큰베이스 B 번호를 저장하는 가장 좋은 방법은 무엇입니까?

Question

큰 밑수 B를 저장하는 가장 좋은 방법은 오른쪽 시프트 및 최하위 비트 확인과 같은 작업을 효율적으로 수행 할 수 있도록하는 것입니다.

사실, 난 내가 생각하는 나는 base N number system을 고려하는 경우, 다음 N^N 그것에 1 followed by N zero에 해당 될 것입니다

Given two numbers N and K such that 0<=N<=1000 and 0<=K<=1000^1000. I need 
to check that whether N^N = K or not. For example: 

if N=2 and K=4 , 2^2 = 4 so return true; 
if N=3 and K=26 , 3^3 != 26 so return false 

말한다 인터뷰 질문 건너 온있다. 예를 들어 - N = 2, 2^2 = 100 (2 진수), N = 3, 3^3 = 1000 (3 진수). 그러면 쉽게 K = N^N인지 여부를 알 수있는 함수를 작성할 수 있습니다.

그것을 효율적으로하기 위해

1) An unsigned long int is not sufficient to store large numbers of range 0 
to 1000^1000. 
2) The modulus and the division operations makes it every less efficient. 

, 나는 몇 가지 방법을 찾고 있어요 내가 오른쪽 시프트를 수행 할 수 있도록 큰 기본 N 번호를 나타내는 :

int check(unsigned long int N, unsigned long int K) 
{ 
    unsigned long int i; 
    for (i=0; i<N; i++) 
    { 
     if (K%N != 0) //checking whether LSB is 0 or not in base N number system 
      return 0; 
     K = K/N; //right shift K by one. 
    } 
    return (K==1); 
} 

이제이 기능 두 가지 문제가있다 최하위 비트 연산들을 효율적으로 체크하는 단계를 포함한다. 누구도 전에 그런 것을 보았습니까? 아니면 누구든지이 문제를 효율적으로 해결할 다른 방법을 알고 있습니까?

Answer 1

왜 숫자를 기본 N으로 변환 하시겠습니까?

당신은 N으로 나누는 것을 계속할 수 있습니다. 만약 당신이 N과 같은 divisons 후에 1을 얻으면 그것은 N^N입니다. 그렇지 않으면 그렇지 않습니다.

문자열로 K를 저장하고 divison 연산을 구현해야합니다. 당신은 http://en.wikipedia.org/wiki/Chinese_remainder_theorem을 사용할 수 있습니다 -

이 파이썬에

divide(k,n): 
    c = '' 
    a = '' 
    for i in k: 
    c = c+i 
    a = a+ str(int(c)/ int(n)) 
    c = str(int(c) % int(n)) 
return a 

, 당신은 당신이 실제로 고정밀 연산을 할 필요가 없습니다 평등을 확인하려면 C

Answer 2

에서 비슷한 구현할 수 있습니다. 그들의 곱이 N^N보다 큰지를 확인하기위한 충분한 소수를 찾은 다음 K = N을 N에 대입하여 각 소수를 차례로 검사하십시오.

실제로는 Java 순차 계산을 위해 Java BigInteger 패키지를 사용합니다.

Answer 3

면접관에 따라 몇 가지 대답이있을 수 있습니다. 그리고 이들 중 어느 하나가 받아 들여지지 않는다면, 면접관이 다른 것을 제안하기 위해 당신을 신속히 움직이게되기를 바랍니다.

• 사용 gmp, 그리고 하나는 N^N을 계산하고 K과 비교 다른 mpz_t 대신 unsigned long 또는 당신의 부서 및 moduluses을한다. 이것은 작동하는 가장 단순한 것입니다.
• 입력이 10 진수이고 2 진수로 변환하는 것보다 빠를 수도 있다고 생각하면 기본 2를 기본 표현으로 사용하지 않고 기본 표현 10을 사용하여 큰 숫자 라이브러리를 작성하십시오. 물론 완전한 산술 라이브러리 일 필요는 없으며, 나머지는 div-with-remainder입니다.
• K이 어떤 점에서 N^N 근처에 없을 때 많은 작업을 피하기 위해 시작하기 전에 할 수있는 몇 가지 빠른 테스트를 만듭니다. 예를 들어, log(K)/N이 log(N)과 거의 같은지 여부를 테스트하고 로그를 입력에 가장 적합한 기본 단위로 취합니다.또는 K 및 N이 2 또는 10과 같은 편리한 번호로 나눌 수 있는지 테스트합니다. 이 정확히 N 번으로 N 번으로 나눌 수없는 경우 분명히 잘못되었습니다. 또는 그들이 동등한 지 여부를 시험해보십시오 (예 : ULONG_MAX 또는 1000000). 불행히도 이런 종류의 문제는 평등하지 않은 특정 사례의 속도를 높이기 만하는 경우를 포함하여 모든 상황을 저해시킵니다. 따라서 예상되는 입력에 따라 비생산적 일 수 있습니다.

mcdowella의 답변이 좋지 않을 수도 있습니다. 잘 모르겠습니다. 특히 프로그램을 작성할 때 한 번만 소수를 생성하면되고, 1009에서 시작하는 1000 소수는 N <= 1000만큼 충분합니다. 큰 소수는 ULONG_MAX의 제곱근보다 커지지 않으면 필요한 작업이 적어 작업이 적다는 것을 의미합니다. 지수를 사용하여 제곱 또는 등가물을 사용하여 N^N을 각 소수로 모듈화하고 K에 대해 입력이되는 기준으로 한 번에 몇 자리 수를 수행합니다.

실제로 깜박이기 위해서는 사전 선택된 소수 인 각각 p에 대해 모든 제수에 대해 작동하는 일반 정수 모듈 연산보다 빠른 modulo-p 연산을 작성 (또는 컴파일러에서 작성할 수 있음) 할 수 있습니다. 즉, 알맞은 컴파일러를 사용하면 j의 값이 컴파일시 알 수없는 i % j보다 빠를 수 있지만 런타임시에는 1009가됩니다. 그러나 속도의 차이가 비용을 정당화 할 수는 없습니다 (예 :) 함수 포인터를 통해 그것을 호출합니다. 그래서 그것을 이용하면 추악한 모양의 반복적 인 코드가 필요할 수 있습니다.

Answer 4

개의 숫자 N과 K되도록 < < = N = 1000 0 0 < < = K = 1000^1,000 감안. N^N = K인지 여부를 확인해야합니다.

많은 것들이 코드에 제공 될 때 저장되는 방법에 따라 달라집니다. 그것들이 텍스트 형식이라고 가정하면, 저는 그것들을 그대로 유지하고 N^N 값을 저장하는 1001 개의 문자열 배열을 만듭니다. 이러한 문자열의 일회성 작성을 루프로 호출하여 bc과 같은 임의 정밀도 산술 명령 줄 프로그램을 사용할 수 있습니다.

Answer 5

1000^1000에서 1000 개의 "양호한"값이 나오기 때문에 (대단히 멀리 떨어져있을 것입니다.) 어떤 로그 대수를 사용하여 N에 대한 추측을 먼저 가질 수 있습니다. 그 후에, 당신은 많아야 하나의 정확한 수표 (예를 들면 bignum 라이브러리로)를 필요로 할 것입니다.

이 대수는 정확하지 않아도됩니다. strlen()은 충분히 근접 할 수 있습니다.