Получение определенной цифры из разложения отношения в любой базе (n-я цифра x / y)

https://stackoverflow.com/questions/804934

03-07-2019
|

Вопрос

Существует ли алгоритм, который может вычислять цифры повторяющегося десятичного отношения, не начиная с самого начала?

Я ищу решение, которое не использует целые числа произвольного размера, поскольку это должно работать для случаев, когда десятичное разложение может быть сколь угодно длинным.

Например, 33/59 преобразуется в повторяющуюся десятичную дробь с 58 цифрами.Если бы я хотел проверить это, как я мог бы вычислить цифры, начинающиеся с 58-го места?

Отредактировано - с соотношением 2124679 / 2147483647, как получить сотню цифр в диапазоне с 2147484600-го по 2147484700-е места.

Решение

Ладно, 3-я попытка - это прелесть :)

Я не могу поверить, что забыл о модульном возведении в степень.

Итак, чтобы подвести итог из моего 2-го ответа, n-я цифра x / y является 1-й цифрой (10^n-1x mod y)/y = этаж (10 * (10^n-1x mod y) / y) mod 10.

Часть, которая занимает все время, - это 10^n-1 mod y, но мы можем сделать это с помощью быстрого (O(log n)) модульного возведения в степень.Учитывая это, не стоит пытаться выполнять алгоритм поиска циклов.

Однако вам нужна возможность выполнять (a * b mod y), где a и b - числа, которые могут быть такими же большими, как y .(если y требует 32 бита, то вам нужно выполнить умножение 32x32, а затем 64-битное % 32-битного модуля, или вам нужен алгоритм, который обходит это ограничение.Смотрите мой список ниже, поскольку я столкнулся с этим ограничением с помощью Javascript.)

Итак, вот новая версия.

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() и модульное возведение в степень одно и то же;оба они основаны на Умножение русского крестьянина.) И результаты:

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 баллов)

Запишите q = x/ y = x/(2^a₂5^a₅z).Множители 2 и 5 в знаменателе не приводят к повторению десятичных дробей.Таким образом, оставшийся коэффициент z равен 10.Фактически, следующий шаг требует факторизации z, так что вы с таким же успехом можете разложить все по факторам.

Вычислить a₁₀ = макс(а₂, а₅), который является наименьшим показателем из 10, кратным множителям 2 и 5 в y.

В нашем примере 57820 = 2 * 2 * 5 * 7 * 7 * 59, итак, a₂ = 2, а₅ = 1, а₁₀ = 2, z = 7 * 7 * 59 = 2891.

В нашем примере 33/59, 59 является простым числом и не содержит множителей 2 или 5, поэтому₂ = a₅ = a₁₀ = 0.

В нашем примере 44/65, 65 = 5*13, и a₂ = 0, a₅ = a₁₀ = 1.

Просто для справки я нашел хороший онлайн-калькулятор факторинга здесь.(даже выполняет то, что важно для следующего шага)

Шаг 2:Использование Теорема Эйлера или Теорема Кармайкла.

То, что нам нужно, - это число n, такое, что 10ⁿ - 1 делится на z, или, другими словами, на 10ⁿ ≡ 1 мод z.Функция Эйлера φ (z) и функция Кармайкла λ (z) дадут вам действительные значения для n, причем λ (z) даст вам меньшее число, а φ (z), возможно, немного легче вычислить.Это не так уж сложно, это просто означает разложение на множители z и небольшую математику.

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

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

Это означает , что 10²⁴³⁶ ≡ 10¹²¹⁸ ≡ 1 (мод 2891).

Для более простой дроби 33/59 φ(59) = λ(59) = 58, поэтому 10⁵⁸ ≡ 1 (мод 59).

Для 44/65 = 44/(5*13), φ(13) = λ(13) = 12.

Ну и что? Что ж, период повторяющейся десятичной дроби должен делить как φ (z), так и λ (z), поэтому они эффективно дают вам верхние границы периода повторяющейся десятичной дроби.

Шаг 3:Еще больше хрустящих чисел

Давайте используем n = λ(z).Если мы вычтем Q' = 10^a₁₀x/y из Q" = 10^{(а₁₀ + n)}x/y, мы получаем:

m = 10^a₁₀(10ⁿ - 1)x/y

который является целым числом потому что 10^a₁₀ является кратным множителям 2 и 5 из y, а также 10ⁿ-1 кратно оставшимся множителям y.

Что мы здесь сделали, так это сдвинули исходное число q влево на a₁₀ места, где нужно получить Q', и сдвинуть влево q на₁₀ + n мест для получения Q", которые являются повторяющимися десятичными числами, но разница между ними - целое число, которое мы можем вычислить.

Тогда мы можем переписать x / y как m / 10^a₁₀ / (10ⁿ - 1).

Рассмотрим пример q = 44/65 = 44/(5*13)

a₁₀ = 1, а λ(13) = 12, так что Q' = 10¹q и Q" = 10¹²⁺¹q.

m = Q" - Q' = (10¹² - 1) * 10¹ * (44/65) = 153846153846*44 = 6769230769224

итак , q = 6769230769224 / 10 / (10¹² - 1).

Другие фракции 33/57820 и 33/59 приводят к образованию более крупных фракций.

Шаг 4:Найдите неповторяющиеся и повторяющиеся десятичные части.

Обратите внимание, что для k от 1 до 9, k/9 = 0.ккккккккккккк...

Аналогично заметим, что двухзначное число kl находится в диапазоне от 1 до 99, k /99 = 0.klklklklklklkl...

Это обобщает:для k-значных шаблонов abc...ij это число abc...ij/(10^k-1) = 0.abc...ijabc...ijabc...ij...

Если вы будете следовать шаблону, то увидите, что нам нужно сделать, это взять это (потенциально) огромное целое число m, которое мы получили на предыдущем шаге, и записать его как m = s *(10ⁿ-1) + r, где 1 ≤ r < 10ⁿ-1.

Это приводит к окончательному ответу:

s - неповторяющаяся часть
r - повторяющаяся часть (при необходимости дополняется нулем слева, чтобы убедиться, что это n цифр).
с помощью₁₀ = 0, запятой между неповторяющимися и повторяющимися часть;если a₁₀ > 0, то он находится a₁₀ места слева от перекрестка между s и r.

Для 44/65 мы получаем 6769230769224 = 6 * (10¹²-1) + 769230769230

s = 6, r = 769230769230 и 44/65 = 0,6769230769230, где подчеркивание здесь обозначает повторяющуюся часть.

Вы можете уменьшить числа, найдя наименьшее значение n на шаге 2, начав с функции Кармайкла λ(z) и посмотрев, приводит ли какой-либо из ее факторов к значениям n таким, что 10ⁿ ≡ 1 (mod z).

Обновить: Для любопытных, интерпретатор Python, по-видимому, является самым простым способом вычисления с помощью bignums.(pow(x,y) вычисляет x^y, а // и % - целочисленное деление и остаток соответственно.) Вот пример:

>>> 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

с перегруженным Python % строковый оператор, используемый для заполнения нулем, чтобы увидеть полный набор повторяющихся цифр:

>>> "%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 (пример:6-я цифра из 1/7 - это 5-я цифра из 10/7 - это 4-я цифра из 100/7 и т.д.)
n-я цифра x / y - это n-я цифра (x%y)/y (пример:5-я цифра 10/7 также является 5-й цифрой 3/7)

Мы можем настроить это так, чтобы это была итеративная процедура, и объединить ее с Алгоритм поиска циклов Флойда (о котором я узнал как о методе "rho" из колонки Мартина Гарднера), чтобы получить что-то, что сокращает этот подход.

Вот функция javascript, которая вычисляет решение с помощью этого подхода:

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

Ad hoc У меня нет хорошей идеи.Может быть непрерывные дроби могу помочь.Я собираюсь немного подумать об этом ...

Обновить

От Маленькая теорема Ферма и поскольку 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