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

Question

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

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

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

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

Answer 1

ОК, 3-я попытка это очарование:)

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

Таким образом, чтобы украсть / суммировать из моего второго ответа, n-ая цифра x / y - это 1-ая цифра (10 ^n-1 x mod y) / y = floor (10 * (10 *) 1007 * n-1 x 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

Answer 2

edit: (Я оставляю пост здесь для потомков. Но , пожалуйста больше не высказывайте это: это может быть теоретически полезно, но не очень практично. Я разместил другой ответ, который гораздо более полезен с практической точки зрения, не требует факторинга и не требует использования 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, так что вы могли бы также сгенерировать все целое.

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

В нашем примере 57820 = 2 * 2 * 5 * 7 * 7 * 59, поэтому ₂ = 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.

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

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

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

(2891) = 7 * 6 * 58 = 2436

& lambda; (2891) = 1 см (7 * 6, 58) = 1218

Это означает, что 10 ²⁴³⁶ & экв .; 10 ¹²¹⁸ & экв .; 1 (мод 2891).

Для более простой фракции 33/59: (59) = & lambda; (59) = 58, поэтому 10 ⁵⁸ и эквивалент; 1 (мод 59).

Для 44/65 = 44 / (5 * 13), & phi; (13) = & lambda; (13) = 12.

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

Шаг 3: Хруст номера

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

m = 10 ^{a ₁₀} (10 ⁿ - 1) х / у

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

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

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

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

a ₁₀ = 1 и & lambda; (13) = 12, поэтому Q '= 10 ¹ q и Q' '= 10 ^{12 + 1} д.

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

Аналогично обратите внимание, что двузначное число kl от 1 до 99, k / 99 = 0.klklklklklkl ...

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

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

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

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

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

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

Вы можете уменьшить числа, найдя наименьшее значение n на шаге 2, начав с функции Кармайкла & lambda; (z) и выяснив, приводит ли какой-либо из ее факторов к значениям n, таким, что 10 ⁿ & экв .; 1 (мод 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'

Answer 3

AHA! caffiend: ваш комментарий к моему другому (более длинному) ответу (в частности, «дублирующиеся остатки») приводит меня к очень простому решению, которое является 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

Answer 4

Как общая методика, рациональные дроби имеют неповторяющуюся часть, за которой следует повторяющаяся часть, например:

nnn.xxxxxxxxrrrrrr

xxxxxxxx является неповторяющейся частью, а rrrrrr является повторяющейся частью.

1. Определите длину неповторяющейся части.
2. Если рассматриваемая цифра находится в неповторяющейся части, рассчитайте ее непосредственно, используя деление.
3. Если рассматриваемая цифра находится в повторяющейся части, вычислите ее положение в повторяющейся последовательности (теперь вы знаете длину всего) и выберите правильную цифру.

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

Answer 5

Ad hoc. Понятия не имею. Может быть продолжение фракций может помочь. Я собираюсь немного подумать об этом ...

UPDATE

Из маленькая теорема Ферма и поскольку 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 - первая цифра после десятичной запятой - мы разработчики)

* * Пример тысячи сорок четыре * * 1045

a = 3
b = 7
p = 6

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

c = 142,857 * 3
  = 428,571

Заполнение не требуется, и мы заключаем.

3     ______
- = 0.428571
7