BigInt를 사용하지 않고 계산

Question

BigInt를 사용하지 않고 n^1000의 값을 인쇄하는 방법은 무엇입니까? 는 일종의 시프트 로직을 사용하는 것에 대해 생각해 왔지만 아직 좋은 것을 제시하지 못했습니다.

Answer 1

확실히 할 수 있으며 운동으로 좋습니다. 그 외에도 기존의 BigInteger 구현을 사용하는 언어로이를 구현할 이유는 거의 없습니다.

연습을 원할 경우, 즉시 BigIntegers를 지원하는 언어로 작업하는 것이 좋습니다. 그렇게하면 BigInteger 연산을 대체 할 때까지 점차적으로 BigInteger 연산을 대체 할 수 있습니다.

BigInteger 라이브러리는 일반적으로 byte 또는 int와 같은 기본 유형의 배열을 사용하여 최대 프리미티브보다 큰 값을 나타냅니다. 다음은 내가 서명 한 바이트 (UByte)와 부호없는 바이트 (BigUInt) 목록을 작성한 파이썬입니다. 여러 개의 UBytes가있는 모든 BigUInt는 인덱스 0을 최상위 바이트로 처리하여 빅 엔디안 표현으로 만듭니다. 반대로하는 것도 좋습니다.

class UByte: 
    def __init__(self, n=0): 
     n = int(n) 
     if (n < 0) or (n >= 255): 
      raise ValueError("Expecting integer in range [0,255).") 
     self.__n = n 

    def value(self): 
     return self.__n 

class BigUInt: 
    def __init__(self, b=[]): 
     self.__b = b 

    def value(self): 
     # treating index 0 as most-significant byte (big endian)                     
     byte_count = len(self.__b) 
     if byte_count == 0: 
      return 0 

     result = 0 
     for i in range(byte_count): 
      place_value = 8 * (byte_count - i - 1) 
      byte_value = self.__b[i].value() << place_value 
      result += byte_value 
     return result 

    def __str__(self): 
     # base 10 representation                             
     return "%s" % self.value() 

위 코드는 사용자가 원하는대로하지 않습니다. BigUInt#value의 여러 부분은 파이썬의 기본 제공 BigIntegers에 의존합니다. 예를 들어 place_value이 실제로 큰 경우에도 byte_value의 계산을 위해 왼쪽 시프트가 오버플로되지 않습니다. 하위 레벨 기계어 코드에서 각 값은 고정 된 비트 수를 가지므로주의하지 않고 왼쪽으로 시프트하면 정보가 손실 될 수 있습니다. 비슷하게, result을 업데이트하는 += 작업은 결국 하위 레벨 코드에서 같은 이유로 오버 플로우되지만 Python이이를 처리합니다.

__str__은 value()을 호출하여 구현됩니다. 파이썬의 마법을 우회하는 한 가지 방법은 __str__을 다시 구현하여 value()을 호출하지 않는 것입니다. 이진수를 10 진수의 문자열로 변환하는 방법을 설명합니다. 완료되면 value()을 으로 간단히 구현할 수 있습니다.

다음은 위의 코드에 대한 몇 가지 샘플 테스트입니다. 그들은 코드를 재 작업하는 동안 온전한 체크로 도움을 줄 수 있습니다.

ten_as_byte = UByte(10) 
ten_as_big_uint = BigUInt([UByte(10)]) 
print "ten as byte ?= ten as ubyte: %s" % (ten_as_byte.value() == ten_as_big_uint.value()) 

three_hundred = 300 
three_hundred_as_big_uint = BigUInt([UByte(0x01), UByte(0x2c)]) 
print "three hundred ?= three hundred as big uint: %s" % (three_hundred == three_hundred_as_big_uint.value()) 

two_to_1000th_power = 2**1000 
two_to_1000th_power_as_big_uint = BigUInt([UByte(0x01)] + [UByte() for x in range(125)]) 
print "2^1000 ?= 2^1000 as big uint: %s" % (two_to_1000th_power == two_to_1000th_power_as_big_uint.value()) 

편집는 : 필요 무슨의 더 낮은 수준의 설명은 From NAND to Tetris 교육 과정의 제 2 장을 참조하십시오. 이 장의 프로젝트는 16 비트 ALU (산술 논리 단위)를 구현하는 것입니다. 그런 다음 ALU를 확장하여 오버플로 비트를 출력하면 임의의 수의 ALU를 함께 연결하여 임의로 큰 입력 번호에 대한 기본 계산을 처리 할 수 ​​있습니다.

Answer 2

정상적인 정수 변수에 적합한 소수를 높게 만드는 것은 구현하기 가장 쉬운 큰 정수 연산 중 하나이며 사람들이 큰 정수 계산을 발견 할 수있게 해주는 작업으로 자주 사용됩니다 원칙.

C에서 다른 많은 예제를 포함하여 좋은 토론은 코드 검토에서 Sum of digits in a^b 이상의 주제에 있습니다. My contribution there은 일종의 '가짜'큰 정수로 std::vector<uint32_t>을 사용하여 반복 제곱을 통해 빠른 지수 연산을 수행하는 방법을 보여줍니다. 그러나 그 주제에서 더 간단한 솔루션이 있습니다. 그냥 선택하십시오.

큰 정수 라이브러리를 검색하지 않고도 C/C++ 큰 정수 코드를 쉽게 테스트 할 수있는 방법은 Visual C++ (Express)에서 관리되는 C++로 코드를 컴파일하는 것입니다.NET의 BigInteger 클래스 : 당신이 할 수 물론

#using "System.Numerics.dll" 
using System::Numerics::BigInteger; 

BigInteger n = BigInteger::Parse("123456789"); 

System::Console::WriteLine(n.Pow(1000));