الحصول على رقم محدد من توسيع النسبة في أي قاعدة (الرقم n من x/y)

https://stackoverflow.com/questions/804934

03-07-2019
|

سؤال

هل هناك خوارزمية يمكنها حساب أرقام النسبة العشرية المتكررة دون البدء من البداية؟

أنا أبحث عن حل لا يستخدم الأعداد الصحيحة ذات الحجم العشوائي، حيث يجب أن يعمل هذا في الحالات التي قد يكون فيها التوسع العشري طويلًا بشكل تعسفي.

على سبيل المثال، يتم توسيع 33/59 إلى رقم عشري متكرر مكون من 58 رقمًا.إذا أردت التحقق من ذلك، كيف يمكنني حساب الأرقام بدءًا من المركز 58؟

تم التحرير - مع النسبة 2124679 / 2147483647، كيفية الحصول على مائة رقم في الأماكن من 2147484600 إلى 2147484700.

المحلول

وOK، محاولة 3rd 'دا سحر:)

وأنا لا أستطيع أن أصدق أنني نسيت عن الأسي وحدات.

وذلك لسرقة / تلخيص من جوابي 2ND، الرقم الألف من س / ص هو الرقم 1ST (10 <سوب> ن 1 س ص وزارة الدفاع) / ص = الكلمة (10 * (10 <سوب> ن 1 س ص وزارة الدفاع) / ذ) وزارة الدفاع 10.

والجزء الذي يأخذ كل الوقت هو 10 <سوب> ن 1 ذ وزارة الدفاع، ولكن يمكننا أن نفعل ذلك مع سرعة (O (سجل ن)) الأسي وحدات. مع هذا في مكان، انها لا تستحق تحاول أن تفعل خوارزمية لتقصي دورة.

ومع ذلك، كنت بحاجة إلى القدرة على القيام (أ * ب ذ وزارة الدفاع) حيث a و b الأرقام التي قد تكون كبيرة كما ذ. (إذا ذ يتطلب 32 بت، ثم ما عليك القيام به ضرب 32x32 ثم 64 بت٪ 32 بت معامل، أو تحتاج إلى الخوارزمية التي تلتف حول هذا القيد. بي الإدراج الذي يلي، لأنني واجهت هذا القيد مع جافا سكريبت. )

وحتى هنا في النسخة الجديدة.

function abmody(a,b,y)
{
  var x = 0;
  // binary fun here
  while (a > 0)
  {
    if (a & 1)
      x = (x + b) % y;
    b = (2 * b) % y;
    a >>>= 1;
  }
  return x;
}

function digits2(x,y,n1,n2)
{
  // the nth digit of x/y = floor(10 * (10^(n-1)*x mod y) / y) mod 10.
  var m = n1-1;
  var A = 1, B = 10;
  while (m > 0)
  {
    // loop invariant: 10^(n1-1) = A*(B^m) mod y

    if (m & 1)
    {
      // A = (A * B) % y    but javascript doesn't have enough sig. digits
      A = abmody(A,B,y);
    }
    // B = (B * B) % y    but javascript doesn't have enough sig. digits
    B = abmody(B,B,y);
    m >>>= 1;
  }

  x = x %  y;
  // A = (A * x) % y;
  A = abmody(A,x,y);

  var answer = "";
  for (var i = n1; i <= n2; ++i)
  {
    var digit = Math.floor(10*A/y)%10;
    answer += digit;
    A = (A * 10) % y;
  }
  return answer;
}

و(عليك ملاحظة أن هياكل abmody() والأسي وحدات هي نفسها، وكلاهما يقوم على <لأ href = "http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication#Peasant_multiplication" يختلط = "noreferrer "> الفلاح الروسي الضرب ). والنتائج:

js>digits2(2124679,214748367,214748300,214748400)
20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digits2(122222,990000,100,110)
65656565656
js>digits2(1,7,1,7)
1428571
js>digits2(1,7,601,607)
1428571
js>digits2(2124679,2147483647,2147484600,2147484700)
04837181235122113132440537741612893408915444001981729642479554583541841517920532039329657349423345806

نصائح أخرى

يحرر: (سأترك هذا المنصب هنا للأجيال القادمة.لكن لو سمحت لا تصوت عليه بعد الآن:قد يكون مفيدًا من الناحية النظرية ولكنه ليس عمليًا حقًا.لقد نشرت إجابة أخرى أكثر فائدة من وجهة نظر عملية، ولا تتطلب أي عوامل، ولا تتطلب استخدام Bignums.)

أعتقد أن @ دانييل بروكنر لديه النهج الصحيح.(مع بعض التقلبات الإضافية المطلوبة)

ربما هناك طريقة أبسط، ولكن ما يلي سيعمل دائمًا:

ولنستخدم الأمثلة q = x/y = 33/57820 و44/65 بالإضافة إلى 33/59، لأسباب قد تتضح بعد قليل.

الخطوة 1:عامل المقام (على وجه التحديد عامل 2 و 5)

اكتب ف = س/ص = س/(2^أ₂5^أ₅ض).عوامل 2 و 5 في المقام لا تسبب أعدادًا عشرية متكررة.وبالتالي فإن العامل المتبقي z هو coprime إلى 10.في الواقع، الخطوة التالية تتطلب تحليل z، لذلك يمكنك أيضًا تحليل الأمر برمته.

احسب أ₁₀ = الحد الأقصى (أ₂, ، أ₅) وهو أصغر أس للعدد 10 وهو مضاعف لعوامل 2 و5 في y.

في مثالنا 57820 = 2 * 2 * 5 * 7 * 7 * 59، إذن₂ = 2، أ₅ = 1، أ₁₀ = 2، ض = 7 * 7 * 59 = 2891.

في مثالنا 33/59، 59 هو عدد أولي ولا يحتوي على عوامل 2 أو 5، لذلك₂ = أ₅ = أ₁₀ = 0.

في مثالنا 44/65، 65 = 5*13، و أ₂ = 0، أ₅ = أ₁₀ = 1.

للإشارة فقط، وجدت آلة حاسبة جيدة للتخصيم عبر الإنترنت هنا.(حتى يفعل ذلك مع العملاء وهو أمر مهم للخطوة التالية)

الخطوة 2:يستخدم نظرية أويلر أو نظرية كارمايكل.

ما نريده هو رقم n مثل 10^ن - 1 يقبل القسمة على z، أو بمعنى آخر 10^ن ≡ 1 مود ض.ستعطيك دالة أويلر φ(z) ودالة كارمايكل φ(z) قيمًا صالحة لـ n، حيث تمنحك φ(z) الرقم الأصغر وربما يكون حساب φ(z) أسهل قليلًا.هذا ليس بالأمر الصعب للغاية، فهو يعني فقط تحليل Z وإجراء القليل من العمليات الحسابية.

φ(2891) = 7 * 6 * 58 = 2436

φ(2891) = lcm(7*6, 58) = 1218

وهذا يعني أن 10²⁴³⁶ ≡ 10¹²¹⁸ ≡ 1 (موديل 2891).

بالنسبة للكسر الأبسط 33/59، φ(59) = lect(59) = 58، إذن 10⁵⁸ ≡ 1 (موديل 59).

بالنسبة إلى 44/65 = 44/(5*13)، φ(13) = lect(13) = 12.

وماذا في ذلك؟ حسنًا، يجب أن تقسم فترة العلامة العشرية المتكررة كلا من φ(z) و lect(z)، لذا فهي تعطيك بشكل فعال الحدود العليا لفترة العلامة العشرية المتكررة.

الخطوه 3:المزيد من طحن الأرقام

دعونا نستخدم n = lect(z).إذا طرحنا Q' = 10^أ₁₀س/ص من Q'' = 10^{(أ₁₀ + ن)}س/ص نحصل على:

م = 10^أ₁₀(10^ن - 1)س/ص

وهو عدد صحيح لأن 10^أ₁₀ هو مضاعف لعوامل 2 و 5 لـ y و 10^ن-1 هو أحد مضاعفات العوامل المتبقية لـ y.

ما فعلناه هنا هو تحويل الرقم الأصلي q بمقدار a إلى اليسار₁₀ أماكن للحصول على Q'، والتحول إلى اليسار q بمقدار a₁₀ + n أماكن للحصول على Q''، وهي أعداد عشرية متكررة، ولكن الفرق بينها هو عدد صحيح يمكننا حسابه.

ثم يمكننا إعادة كتابة x/y كـ m / 10^أ₁₀ / (10^ن - 1).

خذ بعين الاعتبار المثال ف = 44/65 = 44/(5*13)

أ₁₀ = 1، و lect(13) = 12، إذن Q' = 10¹ف و س '' = 10¹²⁺¹س.

م = س'' - س' = (10¹² - 1) * 10¹ * (44/65) = 153846153846*44 = 6769230769224

إذن ف = 6769230769224 / 10 / (10¹² - 1).

الكسور الأخرى 33/57820 و33/59 تؤدي إلى كسور أكبر.

الخطوة 4:العثور على الأجزاء العشرية غير المتكررة والمتكررة.

لاحظ أنه بالنسبة لـ k بين 1 و9، k/9 = 0.kkkkkkkkkkkkk...

وبالمثل لاحظ أن الرقم المكون من رقمين kl بين 1 و99، k/99 = 0.klklklklklkl...

هذا يعمم:بالنسبة لأنماط k-digit abc...ij، هذا الرقم abc...ij/(10^ك-1) = 0.abc...ijabc...ijabc...ij...

إذا اتبعت النمط، فسترى أن ما يتعين علينا القيام به هو أن نأخذ هذا العدد الصحيح الضخم (المحتمل) m الذي حصلنا عليه في الخطوة السابقة، ونكتبه بالشكل m = s*(10)^ن-1) + r، حيث 1 ≥ r < 10^ن-1.

وهذا يؤدي إلى الإجابة النهائية:

s هو الجزء غير المتكرر
r هو الجزء المكرر (مبطن بصفر على اليسار إذا لزم الأمر للتأكد من أنه مكون من أرقام n)
مع₁₀ = 0 ، النقطة العشرية هي بين الجزء غير التكرار والتكرار ؛اذا كان₁₀ > 0 ثم يقع₁₀ أماكن إلى يسار التقاطع بين S و R.

بالنسبة إلى 44/65، نحصل على 6769230769224 = 6 * (10)¹²-1) + 769230769230

s = 6، r = 769230769230، و44/65 = 0.6769230769230 حيث يشير التسطير هنا إلى الجزء المتكرر.

يمكنك تصغير الأرقام من خلال إيجاد أصغر قيمة لـ n في الخطوة 2، وذلك بالبدء بدالة كارمايكل lect(z) ومعرفة ما إذا كان أي من عواملها يؤدي إلى قيم n مثل 10^ن ≡ 1 (mod z).

تحديث: بالنسبة للفضوليين، يبدو أن المترجم بايثون هو أسهل طريقة للحساب باستخدام Bignums.(pow(x,y) يحسب x^ذ, و // و % عبارة عن قسمة عدد صحيح والباقي، على التوالي.) وإليك مثال:

>>> N = pow(10,12)-1
>>> m = N*pow(10,1)*44//65
>>> m
6769230769224
>>> r=m%N
>>> r
769230769230
>>> s=m//N
>>> s
6
>>> 44/65
0.67692307692307696

>>> N = pow(10,58)-1
>>> m=N*33//59
>>> m
5593220338983050847457627118644067796610169491525423728813
>>> r=m%N
>>> r
5593220338983050847457627118644067796610169491525423728813
>>> s=m//N
>>> s
0
>>> 33/59
0.55932203389830504

>>> N = pow(10,1218)-1
>>> m = N*pow(10,2)*33//57820
>>> m
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> r=m%N
>>> r
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> s=m//N
>>> s
0
>>> 33/57820
0.00057073676928398479

مع بايثون المثقلة % مشغل سلسلة قابل للاستخدام للحشوة الصفرية، لرؤية المجموعة الكاملة من الأرقام المتكررة:

>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'

كأسلوب عام، تحتوي الكسور المنطقية على جزء غير متكرر يتبعه جزء متكرر، مثل هذا:

nnn.xxxxxxxxrrrrrr

xxxxxxxx هو الجزء غير المتكرر و rrrrrr هو الجزء المتكرر.

تحديد طول الجزء غير المتكرر.
إذا كان الرقم المعني موجودًا في الجزء غير المتكرر، فاحسبه مباشرة باستخدام القسمة.
إذا كان الرقم المعني موجودًا في الجزء المتكرر، فاحسب موضعه ضمن التسلسل المتكرر (أنت تعرف الآن أطوال كل شيء)، واختر الرقم الصحيح.

ما ورد أعلاه عبارة عن مخطط تقريبي وسيحتاج إلى مزيد من الدقة لتنفيذه في خوارزمية فعلية، ولكنه يجب أن يساعدك على البدء.

آها!كافيند:تعليقك على إجابتي الأخرى (الأطول) (على وجه التحديد "البقايا المكررة") يقودني إلى حل بسيط للغاية وهو O(n) حيث n = مجموع أطوال الأجزاء غير المتكررة + المتكررة، ويتطلب فقط عددًا صحيحًا من الرياضيات الأرقام بين 0 و10*y حيث y هو المقام.

فيما يلي دالة Javascript للحصول على الرقم n الموجود على يمين العلامة العشرية للرقم المنطقي x/y:

function digit(x,y,n) 
{ 
   if (n == 0) 
      return Math.floor(x/y)%10; 
   return digit(10*(x%y),y,n-1);
}

إنها متكررة وليست تكرارية، وليست ذكية بما يكفي لاكتشاف الدورات (من الواضح أن الرقم 10000 من 1/3 هو 3، لكن هذا يستمر حتى يصل إلى التكرار رقم 10000)، ولكنه يعمل على الأقل حتى نفاد المكدس. ذاكرة.

يعمل هذا بشكل أساسي بسبب حقيقتين:

الرقم n من x/y هو الرقم (n-1) من 10x/y (مثال:الرقم السادس من 1/7 هو الرقم الخامس من 10/7 هو الرقم الرابع من 100/7 إلخ.)
الرقم n من x/y هو الرقم n من (x%y)/y (مثال:الرقم الخامس من 10/7 هو أيضًا الرقم الخامس من 3/7)

يمكننا تعديل هذا ليكون روتينًا متكررًا ودمجه معه خوارزمية فلويد للعثور على الدورة (التي تعلمتها بطريقة "rho" من عمود Martin Gardner) للحصول على شيء يختصر هذا النهج.

إليك وظيفة جافا سكريبت التي تحسب الحل باستخدام هذا الأسلوب:

function digit(x,y,n,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  while (n > 0)
  {
    n--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      n = n % period;
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }
  }
  var answer=Math.floor(x1/y);
  if (returnstruct)
    return {period: period, digit: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digit='+this.digit;
      }};
  else
    return answer;
}

ومثال على تشغيل الرقم n من 1/700:

js>1/700
0.0014285714285714286
js>n=10000000
10000000
js>rs=digit(1,700,n,true)
period=6,digit=4
js>n%6
4
js>rs=digit(1,700,4,true)
period=0,digit=4

نفس الشيء بالنسبة لـ 33/59:

js>33/59
0.559322033898305
js>rs=digit(33,59,3,true)
period=0,digit=9
js>rs=digit(33,59,61,true)
period=58,digit=9
js>rs=digit(33,59,61+58,true)
period=58,digit=9

و122222/990000 (الجزء الطويل غير المكرر):

js>122222/990000
0.12345656565656565
js>digit(122222,990000,5,true)
period=0,digit=5
js>digit(122222,990000,7,true)
period=6,digit=5
js>digit(122222,990000,9,true)
period=2,digit=5
js>digit(122222,990000,9999,true)
period=2,digit=5
js>digit(122222,990000,10000,true)
period=2,digit=6

إليك وظيفة أخرى تجد امتدادًا للأرقام:

// find digits n1 through n2 of x/y
function digits(x,y,n1,n2,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  var answer='';
  while (n2 >= 0)
  {
    // time to print out digits?
    if (n1 <= 0) 
      answer = answer + Math.floor(x1/y);

    n1--,n2--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      if (n1 > period)
      {
        var jumpahead = n1 - (n1 % period);
        n1 -= jumpahead, n2 -= jumpahead;
      }
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }    
  }
  if (returnstruct)
    return {period: period, digits: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digits='+this.digits;
      }};
  else
    return answer;
}

لقد قمت بتضمين نتائج إجابتك (بافتراض أن Javascript # لم يتجاوز السعة):

js>digit(1,7,1,7,true)
period=6,digits=1428571
js>digit(1,7,601,607,true)
period=6,digits=1428571
js>1/7
0.14285714285714285
js>digit(2124679,214748367,214748300,214748400,true)
period=1759780,digits=20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digit(122222,990000,100,110,true)
period=2,digits=65656565656

مخصص ليس لدي فكرة جيدة.ربما استمرار الكسور استطيع المساعدة.سأفكر بالأمر قليلاً..

تحديث

~~من نظرية فيرما الصغيرة ولأن 39 عدد أولي فإن العبارات التالية.(= يشير إلى التطابق)~~

10^39 = 10 (39)

لأن 10 هو أولي إلى 39.

10^(39 - 1) = 1 (39) 10^38 - 1 = 0 (39) [to be continued tomorow]

لقد كنت متدرجًا عندما أدركت أن 39 ليس رقمًا أوليًا ...^^ سأقوم بالتحديث والإجابة في الأيام القادمة وتقديم الفكرة بأكملها.شكرًا لملاحظتك أن 39 ليس عددًا أوليًا.

الجواب القصير ل a/b مع a < b وطول الفترة المفترضة p ...

احسب k = (10^p - 1) / b والتحقق من أنه عدد صحيح، وإلا a/b ليس لديه فترة p
احسب c = k * a
يتحول c إلى تمثيله العشري وتركه مع الأصفار بطول إجمالي p
الرقم i بعد العلامة العشرية هو الرقم (i mod p) من التمثيل العشري المبطن (i = 0 هو الرقم الأول بعد العلامة العشرية - نحن مطورون)

مثال

a = 3
b = 7
p = 6

k = (10^6 - 1) / 7
  = 142,857

c = 142,857 * 3
  = 428,571

الحشو غير مطلوب ونستنتج.

3     ______
- = 0.428571
7

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow