모든베이스에서 비율 확장에서 특정 숫자를 얻습니다 (x/y의 n 번째 숫자)

https://stackoverflow.com/questions/804934

03-07-2019
|

문제

처음부터 시작하지 않고 반복 정도의 비율의 숫자를 계산할 수있는 알고리즘이 있습니까?

나는 임의로 크기의 정수를 사용하지 않는 솔루션을 찾고 있습니다. 이는 소수 확장이 임의로 길어질 수있는 경우에 효과가 있어야하기 때문입니다.

예를 들어, 33/59는 58 자리의 반복 소수점으로 확장됩니다. 그것을 확인하고 싶다면 58 위에서 시작하는 숫자를 어떻게 계산할 수 있습니까?

편집 - 2124679 / 2147483647 비율로 2147484600th ~ 2147484700th 장소에서 100 자리를 얻는 방법.

해결책

좋아, 세 번째 시도는 매력입니다 :)

모듈 식 지수에 대해 잊어 버린 것을 믿을 수 없습니다.

두 번째 답변에서 훔치거나 요약하기 위해 X/Y의 NTH 자리는 (10의 첫 번째 숫자입니다.^N-1x mod y)/y = 바닥 (10 * (10^N-1x mod y) / y) mod 10.

항상 시간이 걸리는 부분은 10입니다.^N-1 모드 Y이지만 빠른 (O (log n)) 모듈 식 지수로이를 수행 할 수 있습니다. 이것을 사용하면 사이클 찾기 알고리즘을 시도하는 것은 가치가 없습니다.

그러나 a와 b가 y만큼 큰 숫자 인 경우 (a * b mod 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를 사용할 필요가 없습니다.)

@Daniel Bruckner는 올바른 접근 방식을 가지고 있다고 생각합니다. (몇 가지 추가 비틀기가 필요합니다)

어쩌면 더 간단한 방법이 있지만 다음은 항상 작동합니다.

33/59 외에 예제 q = x/y = 33/57820 및 44/65를 사용해 보겠습니다.

1 단계 : 분모를 고려합니다 (구체적으로 2와 5를 고려합니다)

쓰기 q = x/y = x/(2^ㅏ₂5^ㅏ₅지). 분모에서 2와 5의 요인은 반복 된 소수점을 유발하지 않습니다. 따라서 나머지 계수 z는 10에서 10까지입니다. 실제로 다음 단계는 z를 고려해야하므로 모든 것을 고려할 수 있습니다.

계산 a₁₀ = max (a₂, ㅏ₅) 이는 10의 가장 작은 지수 인 y에서 2와 5의 여러 가지 요인 중 하나입니다.

이 예에서 57820 = 2 * 2 * 5 * 7 * 7 * 59, 그래서 a₂ = 2, a₅ = 1, a₁₀ = 2, z = 7 * 7 * 59 = 2891.

이 예에서 33/59, 59는 프라임이며 2 또는 5의 요인이 없습니다.₂ = a₅ = a₁₀ = 0.

이 예에서 44/65, 65 = 5*13 및₂ = 0, a₅ = a₁₀ = 1.

참조를 위해 좋은 온라인 팩토링 계산기를 찾았습니다. 여기. (다음 단계에 중요한 고통도 마찬가지입니다)

2 단계 : 사용 오일러의 정리 또는 Carmichael의 정리.

우리가 원하는 것은 10이되는 숫자입니다.^N -1은 z로 나눌 수 있거나, 즉, 10^N ≡ 1 mod z. Euler의 함수 φ (z)와 Carmichael의 함수 λ (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을 빼면^ㅏ₁₀q ''= 10에서 x/y^{(ㅏ₁₀ + N)}x/y, 우리는 다음을 얻는다 :

m = 10^ㅏ₁₀(10^N -1) x/y

정수입니다 10이기 때문에^ㅏ₁₀ Y의 2 및 5 요인 중 하나이며 10^N-1은 y의 나머지 요인 중 배수입니다.

우리가 여기서 한 일은 원래 번호 Q를₁₀ Q '를 얻을 수있는 장소, 그리고 Q를 왼쪽으로 이동₁₀ + n Q ''를 얻을 수있는 장소는 소수성을 반복하지만 차이점은 우리가 계산할 수있는 정수입니다.

그런 다음 x / y를 m / 10으로 다시 쓸 수 있습니다.^ㅏ₁₀ / (10^N - 1).

예제 q = 44/65 = 44/(5*13)를 고려하십시오.

ㅏ₁₀ = 1, λ (13) = 12, q '= 10¹Q 및 Q ''= 10¹²⁺¹큐.

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

따라서 Q = 6769230769224 / 10 / (10¹² - 1).

다른 분획 33/57820 및 33/59는 더 큰 분수로 이어집니다.

4 단계 : 비 반복 및 반복되는 소수점 부품을 찾으십시오.

1과 9 사이의 K의 경우 k/9 = 0.kkkkkkkkkkkk ...

마찬가지로 1과 99 사이의 2 자리 숫자 kl, k/99 = 0.klklklklklkl ...

일반화 : k 자지 패턴 ABC ... ij,이 숫자 ABC ... ij/(10^케이-1) = 0.ABC ... ijabc ... ijabc ... ij ...

패턴을 따르는 경우, 우리가해야 할 일은 이전 단계에서 얻은 (잠재적으로) 거대한 정수 M을 취하고 M = S*(10으로 작성하는 것입니다.^N-1) + r, 여기서 1 ≤ r <10^N-1.

이것은 최종 답변으로 이어집니다.

S는 비 반복 부분입니다
r은 반복 부분입니다 (필요한 경우 왼쪽에 제로 패딩이 N 자리임을 확인하기 위해)
a₁₀ = 0, 소수점은 비 반복 및 반복 부분 사이에 있습니다. 만약₁₀ > 0은 a₁₀ s와 r 사이의 교차점 왼쪽의 장소.

44/65의 경우 6769230769224 = 6 * (10¹²-1) + 769230769230

s = 6, r = 769230769230 및 44/65 = 0.6769230769230 여기서 밑줄이 반복 된 부분을 지정합니다.

Carmichael 함수 λ (z)부터 시작하여 그 요인 중 어느 것이 N의 값으로 이어지는 지 확인하여 2 단계에서 N의 가장 작은 값을 찾아서 숫자를 더 작게 만들 수 있습니다.^N ≡ 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 반복되는 부분입니다.

비 반복 부품의 길이를 결정하십시오.
해당 숫자가 반복되지 않은 부분에있는 경우, 부서를 사용하여 직접 계산하십시오.
해당 숫자가 반복되는 부분에있는 경우 반복 시퀀스 내에서 위치를 계산하고 (이제 모든 것의 길이를 알고 있음) 올바른 숫자를 선택하십시오.

위의 것은 대략적인 개요이며 실제 알고리즘으로 구현하려면 더 많은 정밀도가 필요하지만 시작해야합니다.

아하! Caffiend : 다른 (더 긴) 답변에 대한 귀하의 의견 (구체적으로 "나머지 중복")은 O (n) 인 매우 간단한 솔루션으로 이어집니다. 0과 10*y 사이의 수학 여기서 y는 분모입니다.

다음은 NTH 자리를 합리적 번호 X/Y의 소수점 오른쪽으로 가져 오는 JavaScript 기능입니다.

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

그것은 반복적이기보다는 재귀 적이며 사이클을 감지하기에 충분히 똑똑하지 않습니다 (1/3의 100000 자리는 분명히 3이지만 10000 번째 반복에 도달 할 때까지 계속 진행됩니다). 메모리.

기본적으로 이것은 두 가지 사실 때문에 작동합니다.

x/y의 n 번째 숫자는 10x/y의 (n-1) th 숫자입니다 (예 : 1/7의 6 자리는 10/7의 5 자리입니다.
x/y의 n 번째 숫자는 (x%y)/y의 n 번째 숫자입니다 (예 : 10/7의 5 자리도 3/7의 5 자리이기도합니다)

우리는 이것을 반복적 인 루틴으로 조정하고 그것을 결합 할 수 있습니다. 플로이드의 사이클 찾기 알고리즘 (내가 Martin Gardner 칼럼에서 "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;
}

그리고 1/700의 n 번째 숫자를 실행하는 예 :

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 나는 좋은 생각이 없습니다. 아마도 계속 된 분수 도울 수있다. 나는 그것에 대해 조금 생각할 것입니다 ...

업데이트

~~에서 Fermat의 작은 정리 그리고 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 소수점 표현으로, 왼쪽으로 왼쪽으로 패드는 0으로 가득 채우고 있습니다. p
소수점 이후의 I-th 숫자는 패드 된 소수점 표현의 (i mod p) -th 숫자입니다 (i = 0은 10 진수 지점의 첫 번째 숫자입니다-우리는 개발자입니다)

예시

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