많은 숫자로 계수를 수행 하시겠습니까?

StackOverflow https://stackoverflow.com/questions/278440

  •  07-07-2019
  •  | 
  •  

문제

매우 큰 정수에서 모듈러스 작업을 수행해야합니다. 내 플랫폼에서 지원하는 가장 큰 정수 (편집 : .NET 2.0)는 64 비트 정수로 작업하는 숫자에 대해 충분히 크지 않습니다.

126548756326424875387321657498462167853687516876876과 같은 정말 큰 정수에서 모듈러스를 어떻게 할 수 있습니까?

나는 숫자를 문자열로 취급하고 하나씩 조각으로 작동하는 솔루션이 있지만 더 나은 방법이 있는지 알고 싶었습니다.

다음은 숫자를 문자열로 취급하는 내 기능입니다. 그것은 기본적으로 손으로 할 수있는 방식으로 긴 분열을합니다.

    Public Function MyMod(ByVal numberString As String, ByVal modby As Integer) As Integer
        Dim position As Integer = -1
        Dim curSubtraction As Integer = 0

        While position < numberString.Length - 1
            position += 1
            curSubtraction = curSubtraction * 10 + CInt(numberString.Substring(position, 1))

            If (curSubtraction / modby) < 1 And position = numberString.Length - 1 Then
                Return curSubtraction
            ElseIf (curSubtraction / modby) < 1 Then
                Continue While
            Else
                curSubtraction = curSubtraction Mod modby
            End If
        End While
        Return curSubtraction
    End Function

더 깨끗하고 효율적인 방법이 있습니까?

편집 : 명확히하기 위해 정수는 Iban Bank 계좌 번호에서 나옵니다. 사양에 따르면, IBAN 계정 번호 (문자 포함)를 하나의 정수로 변환해야합니다. 그런 다음 정수에서 계수를합니다. 그래서, 나는 당신이 계수를 수행하는 정수의 실제 소스가 일련의 숫자라고 말할 수 있다고 생각합니다.

도움이 되었습니까?

해결책

숫자가 어디에서 오는지 지정하지는 않았지만 단순화를 할 수 있습니다. 숫자가 원래 더 작은 경우 다음과 같은 것을 고려하십시오.

(a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n

또는

ab MOD n = (a MOD n)(b MOD n) MOD n

다른 팁

암호화/수학 라이브러리를 사용하십시오. Bignum의 Google.

다음과 같은 임의의 정수 수학 라이브러리가 필요합니다 intx.

.NET 4를 사용하는 경우 BigInteger 만 사용할 수 있습니다. 그러나 이전 버전으로 수행하는 방법은 다음과 같습니다.

먼저 가져갈 수있는 모드가있는 수학적 트릭이 있습니다. 엑스 숫자 수, 해당 값의 모드를 계산 한 다음 Prepend 결과 그 모드의 남은 숫자로 다시 돌아와서 "거대한"숫자의 끝에 도달 할 때까지 프로세스를 계속 반복하십시오.

재귀 방법을 가져 오십시오! (죄송합니다 VB를하지 않아)

private static int Mod(string value, int mod) {
    if (string.IsNullOrEmpty(value)) throw new ArgumentException("Invalid value.", "value");
    if (mod <= 0) throw new ArgumentException("Invalid mod.", "mod");

    int maxLength = long.MaxValue.ToString().Length - 1;

    return value.Length > maxLength
        ? Mod((Convert.ToInt64(value.Substring(0, maxLength)) % mod).ToString() + value.Substring(maxLength), mod)
        : Convert.ToInt32(Convert.ToInt64(value) % mod);}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top