java.math.BigInteger를 사용하지 않고 Java에서 매우 큰 수를 처리하는 방법
사용하지 않고 임의로 큰 정수를 사용하여 산술 +-/ * %!를 수행하는 방법은 java.math.BigInteger무엇입니까?
예를 들어, 90의 계승은 Java에서 0을 반환합니다. 나는 그것을 해결할 수 있기를 바랍니다.
프로그래머가 자신의 bignum-library를 한 번 구현 했어야한다고 생각하므로 여기에서 환영합니다.
(물론 나중에 BigInteger가 더 낫다는 것을 알게 될 것이며 이것을 사용하지만 귀중한 학습 경험입니다.)
(이 과정의 소스 코드 를 github에서 따를 수 있습니다 . 또한 이것을 14 부로 구성된 블로그 시리즈 로 다시 만들었 습니다 .)
자바로 간단한 Big Number 클래스 만들기
그래서 우리에게 무엇이 필요합니까?
첫째, 숫자의 표현,
Java가 제공하는 데이터 유형을 기반으로합니다.
십진수 변환이 가장 복잡한 부분이라고 생각하므로 십진수 기반 모드를 유지합시다. 효율성을 위해 실제 십진수가 아닌 base로 작업합니다 1 000 000 000 = 10^9 < 2^30. 이것은 Java int( 2^31또는 까지)에 적합하며, 2^32이러한 두 숫자 의 곱은 Java에 잘 맞습니다 long.
final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;
그런 다음 숫자 배열 :
private int[] digits;
작은 또는 큰 엔디안, 즉 큰 부분이 먼저 또는 마지막으로 숫자를 저장합니까? 그것은별로 중요하지 않습니다. 그래서 우리는 이것이 인간이 그것을 읽고 싶어하는 방식이기 때문에 빅 엔디안을 결정합니다. (지금은 음수가 아닌 값에 집중합니다. 나중에 음수에 부호 비트를 추가합니다.)
테스트를 위해 int []에서 초기화 할 수있는 생성자를 추가합니다.
/**
* creates a DecimalBigInt based on an array of digits.
* @param digits a list of digits, each between 0 (inclusive)
* and {@link BASE} (exclusive).
* @throws IllegalArgumentException if any digit is out of range.
*/
public DecimalBigInt(int... digits) {
for(int digit : digits) {
if(digit < 0 || BASE <= digit) {
throw new IllegalArgumentException("digit " + digit +
" out of range!");
}
}
this.digits = digits.clone();
}
추가 보너스로,이 생성자는 단일 int(보다 작은 경우 BASE) 및 아니요 int(0으로 해석 됨)에도 사용할 수 있습니다. 이제 다음과 같이 할 수 있습니다.
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
이것은 우리에게 de.fencing_game.paul.examples.DecimalBigInt@6af62373별로 유용하지는 않습니다. 그래서 우리는 toString()메소드를 추가합니다 :
/**
* A simple string view for debugging purposes.
* (Will be replaced later with a real decimal conversion.)
*/
public String toString() {
return "Big" + Arrays.toString(digits);
}
출력은 이제 Big[7, 5, 2, 12345]이며 테스트에 더 유용하지 않습니까?
둘째, 십진수 형식에서 변환.
여기서 우리는 운이 좋습니다. 우리의 밑수 (10 ^ 9)는 우리가 변환하려는 밑수 (10)의 거듭 제곱입니다. 따라서 우리는 항상 하나의 "우리 형식"숫자를 나타내는 동일한 숫자 (9)의 십진수를가집니다. (물론 처음에는 약간의 숫자가 적을 수 있습니다.) 다음 코드에서 decimal십진수 문자열입니다.
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
이 이상한 공식은 Java int 작성 방식입니다 bigLen = ceil(decLen/BASE_DECIMAL_DIGITS). (정확했으면 좋겠습니다. 나중에 테스트하겠습니다.)
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
10 진수의 첫 번째 블록 길이이며 1에서 9 (포함) 사이 여야합니다.
배열을 만듭니다.
int[] digits = new int[bigLen];
생성 할 숫자를 반복 :
for(int i = 0; i < bigLen ; i++) {
각각의 우리 숫자는 원 전화 번호의 자릿수의 블록으로 표시된다 :
String block =
decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
firstSome + i *BASE_DECIMAL_DIGITS);
( Math.max여기서는 첫 번째 더 짧은 블록에 필요합니다.) 이제 일반적인 Integer 구문 분석 함수를 사용하고 결과를 배열에 넣습니다.
digits[i] = Integer.parseInt(block);
}
이제 생성 된 배열에서 DecimalBigInt 객체를 생성합니다.
return new DecimalBigInt(digits);
이것이 작동하는지 봅시다 :
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
산출:
Big[12, 345678901, 234567890]
맞아 보인다 :-) 우리는 길이가 다른 다른 숫자로도 테스트해야합니다.
다음 부분은 십진수 형식이 될 것입니다. 이것은 훨씬 더 쉽습니다.
셋째, 십진수 형식으로 변환합니다.
개별 숫자를 각각 10 진수 9 자리로 출력해야합니다. 이를 위해 Formatterprintf와 유사한 형식 문자열을 지원 하는 클래스를 사용할 수 있습니다 .
간단한 변형은 다음과 같습니다.
public String toDecimalString() {
Formatter f = new Formatter();
for(int digit : digits) {
f.format("%09d", digit);
}
return f.toString();
}
이것은 반환 000000007000000005000000002000012345및 000000012345678901234567890우리의 두 숫자. 이것은 왕복으로 작동하지만 (즉, valueOf메서드에 공급 하면 동등한 객체가 제공됨), 선행 0은보기에 좋지 않습니다 (8 진수와 혼동을 일으킬 수 있음). 따라서 아름다운 for-each 루프를 분리하고 첫 번째 및 다음 숫자에 대해 다른 형식 지정 문자열을 사용해야합니다.
public String toDecimalString() {
Formatter f = new Formatter();
f.format("%d", digits[0]);
for(int i = 1 ; i < digits.length; i++) {
f.format("%09d", digits[i]);
}
return f.toString();
}
부가.
이것은 간단하므로 덧셈부터 시작하겠습니다 (나중에 곱하기 위해 일부를 사용할 수 있음).
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
...
}
난 당신이 이렇게, 공식을 읽을 것처럼 읽을 수있는 방법 이름을 원하는 plus, minus, times대신 add, subtract, multiply.
그렇다면 덧셈은 어떻게 작동합니까? 9보다 큰 10 진수에 대해 학교에서 배운 것과 동일하게 작동합니다. 해당 숫자를 더하고, 결과가 10보다 크면 (또는 BASE우리의 경우) 다음 숫자에 1을 전달합니다. 이로 인해 결과 숫자가 원래 숫자보다 한 자리 더 많을 수 있습니다.
먼저 두 숫자가 동일한 자릿수를 갖는 간단한 경우를 살펴 봅니다. 그러면 간단하게 다음과 같이 보입니다.
int[] result = new int[this.digits.length];
int carry = 0;
for(int i = this.digits.length-1; i > 0; i--) {
int digSum = carry + this.digits[i] + that.digits[i];
result[i] = digSum % BASE;
carry = digSum / BASE;
}
if(carry > 0) {
int[] temp = new int[result.length + 1];
System.arraycopy(result, 0, temp, 1, result.length);
temp[0] = carry;
result = temp;
}
return new DecimalBigInt(result);
(오른쪽에서 왼쪽으로 이동하므로 오버플로를 다음 자릿수로 전달할 수 있습니다. Little Endian 형식을 사용하기로 결정했다면 조금 더 예쁩니다.)
두 숫자의 자릿수가 같지 않으면 조금 더 복잡해집니다.
가능한 한 간단하게하기 위해 몇 가지 방법으로 분할합니다.
이 메서드는 배열의 요소 (이미 0이 아닌 값을 포함 할 수 있음)에 한 자릿수를 추가하고 결과를 배열에 다시 저장합니다. 오버플로가 있으면 재귀 호출을 통해 다음 숫자 (색인이 하나 더 적고 하나 더 적음)로 이동합니다. 이런 식으로 숫자가 항상 유효한 범위에 있도록합니다.
/**
* adds one digit from the addend to the corresponding digit
* of the result.
* If there is carry, it is recursively added to the next digit
* of the result.
*/
private void addDigit(int[] result, int resultIndex,
int addendDigit)
{
int sum = result[resultIndex] + addendDigit;
result[resultIndex] = sum % BASE;
int carry = sum / BASE;
if(carry > 0) {
addDigit(result, resultIndex - 1, carry);
}
}
다음은 추가 할 전체 자릿수 배열에 대해 동일합니다.
/**
* adds all the digits from the addend array to the result array.
*/
private void addDigits(int[] result, int resultIndex,
int... addend)
{
addendIndex = addend.length - 1;
while(addendIndex >= 0) {
addDigit(result, resultIndex,
addend[addendIndex]);
addendIndex--;
resultIndex--;
}
}
이제 plus메서드를 구현할 수 있습니다 .
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
int[] result = new int[Math.max(this.digits.length,
that.digits.length)+ 1];
addDigits(result, result.length-1, this.digits);
addDigits(result, result.length-1, that.digits);
// cut of leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
오버플로가 가능한지 이전에 살펴보고 필요한 것보다 더 큰 배열을 만들면 여기서 조금 더 잘할 수 있습니다.
아, 하나의 테스트 :를 d2.plus(d2)제공합니다 Big[24, 691357802, 469135780].
곱셈.
학교로 돌아가서 어떻게 종이에 더 큰 숫자를 곱했는지 기억합시다.
123 * 123
----------
369 <== 123 * 3
246 <== 123 * 2
123 <== 123 * 1
--------
15129
따라서 첫 번째 숫자의 각 자릿수 [i]와 두 번째 숫자의 각 자릿수 [j]를 곱하고 결과의 자릿수 [i + j]에 곱을 더해야합니다. 물론 여기서 인덱스는 왼쪽이 아닌 오른쪽에서 계산됩니다. (이제 나는 리틀 엔디안 숫자를 사용했으면 좋았을 것입니다.)
두 자리의 곱이 범위를 벗어날 수 있으므로 곱셈에 int사용 long합니다.
/**
* multiplies two digits and adds the product to the result array
* at the right digit-position.
*/
private void multiplyDigit(int[] result, int resultIndex,
int firstFactor, int secondFactor) {
long prod = (long)firstFactor * (long)secondFactor;
int prodDigit = (int)(prod % BASE);
int carry = (int)(prod / BASE);
addDigits(result, resultIndex, carry, prodDigit);
}
이제 매개 변수 addDigits를 사용하도록 메서드를 선언 한 이유를 알 수 있습니다 resultIndex. (그리고 여기에 더 잘 쓸 수 있도록 마지막 인수를 varargs 매개 변수로 변경했습니다.)
따라서 여기 교차 곱셈 방법은 다음과 같습니다.
private void multiplyDigits(int[] result, int resultIndex,
int[] leftFactor, int[] rightFactor) {
for(int i = 0; i < leftFactor.length; i++) {
for(int j = 0; j < rightFactor.length; j++) {
multiplyDigit(result, resultIndex - (i + j),
leftFactor[leftFactor.length-i-1],
rightFactor[rightFactor.length-j-1]);
}
}
}
인덱스 계산이 옳았 으면합니다. 리틀 엔디안 표현을 사용하면 multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j])-상당히 명확 했을 것 입니다. 그렇지 않습니까?
times이제 우리의 메서드는 결과 배열을 할당하고 결과를 호출 multiplyDigits하고 래핑하기 만하면됩니다.
/**
* returns the product {@code this × that}.
*/
public DecimalBigInt times(DecimalBigInt that) {
int[] result = new int[this.digits.length + that.digits.length];
multiplyDigits(result, result.length-1,
this.digits, that.digits);
// cut off leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
테스트를 위해 d2.times(d2)제공 Big[152, 415787532, 388367501, 905199875, 19052100], 무엇을 내 이맥스 CALC 계산 여기 동일하다.
비교
우리는 두 물체를 비교할 수 있기를 원합니다. 그래서 우리는 Comparable<DecimalBigInt>그 compareTo 메소드를 구현 합니다.
public int compareTo(DecimalBigInt that) {
숫자 중 하나가 다른 숫자보다 큰지 어떻게 알 수 있습니까? 먼저 배열의 길이를 비교합니다. 선행 0을 유도하지 않도록주의 했으므로 (그렇습니까?) 배열이 길수록 숫자가 더 커야합니다.
if(this.digits.length < that.digits.length) {
return -1;
}
if (that.digits.length < this.digits.length) {
return 1;
}
길이가 같으면 요소별로 비교할 수 있습니다. 빅 엔디안을 사용하기 때문에 (즉 , 빅 엔드가 먼저옵니다 ) 처음부터 시작합니다.
for(int i = 0; i < this.digits.length; i++) {
if(this.digits[i] < that.digits[i]) {
return -1;
}
if(that.digits[i] < this.digits[i]) {
return 1;
}
}
모든 것이 동일하다면 분명히 우리의 숫자는 동일하며를 반환 할 수 있습니다 0.
return 0;
}
equals + hashCode()
모든 좋은 불변 클래스는 구현해야 equals()하고 hashCode()적절한 (및 호환) 방식이다.
의 경우 hashCode()단순히 숫자를 합산하고 작은 소수를 곱하여 숫자 전환이 동일한 해시 코드를 생성하지 않도록합니다.
/**
* calculates a hashCode for this object.
*/
public int hashCode() {
int hash = 0;
for(int digit : digits) {
hash = hash * 13 + digit;
}
return hash;
}
에서 equals()방법 우리는 단순히 대신 다시 같은 알고리즘을 구현의의 compareTo 메소드에 위임 할 수 있습니다 :
/**
* compares this object with another object for equality.
* A DecimalBigInt is equal to another object only if this other
* object is also a DecimalBigInt and both represent the same
* natural number.
*/
public boolean equals(Object o) {
return o instanceof DecimalBigInt &&
this.compareTo((DecimalBigInt)o) == 0;
}
그래서 오늘은 충분합니다. 빼기 (또는 음수)와 나눗셈은 더 복잡하므로 지금은 생략하겠습니다. 90의 계승을 계산하려면 이것으로 충분합니다.
큰 팩토리얼 계산 :
계승 함수는 다음과 같습니다.
/**
* calculates the factorial of an int number.
* This uses a simple iterative loop.
*/
public static DecimalBigInt factorial(int n) {
DecimalBigInt fac = new DecimalBigInt(1);
for(int i = 2; i <= n; i++) {
fac = fac.times(new DecimalBigInt(i));
}
return fac;
}
이것은 우리에게
fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
임의의 기수 표현에서 변환
frodosamoa에 대한 다음 질문에서 나는 우리가 계산할 수있는 (또는 원하는) 계산할 수있는 임의의 (위치) 수 체계에서 변환하는 방법에 대한 대답을 썼습니다 . (그 예에서 나는 삼진을 십진수로 변환하고 질문은 십진수에서 이진수로 변환했습니다.)
여기서 우리는 임의의 숫자 시스템 (좋아, 2에서 36 사이의 기수를 사용 Character.digit()하여 단일 자릿수를 정수로 변환 하는 데 사용할 수 있음 )에서 기수 BASE(= 1.000.000.000,하지만 여기서는 실제로 중요하지 않음 )를 사용 하는 시스템으로 변환 하려고합니다. .
기본적으로 우리 는 기수로 주어진 점에서 계수로 숫자를 갖는 다항식의 값을 계산하기 위해 Horner 체계 를 사용합니다.
sum[i=0..n] digit[i] * radix^i
이 루프로 계산할 수 있습니다.
value = 0;
for i = n .. 0
value = value * radix + digit[i]
return value
입력 문자열은 빅 엔디안이므로 카운트 다운 할 필요가 없지만 간단한 향상된 for 루프를 사용할 수 있습니다. (자바에서는 연산자 오버로딩이없고 int에서 DecimalBigInt 유형으로의 오토 박싱이 없기 때문에 더보기 흉해 보입니다.)
public static DecimalBigInt valueOf(String text, int radix) {
DecimalBigInt bigRadix = new DecimalBigInt(radix);
DecimalBigInt value = new DecimalBigInt(); // 0
for(char digit : text.toCharArray()) {
DecimalBigInt bigDigit =
new DecimalBigInt(Character.digit(digit, radix));
value = value.times(bigRadix).plus(bigDigit);
}
return value;
}
에서 내 실제 구현 나는 우리가 정말 유효한 숫자를 가지고 있고, 당연히 문서 주석 있도록 몇 가지 오류 검사 (및 예외 던지기)를 추가했다.
임의의 위치 시스템으로 변환 하는 것은 우리가 아직 구현하지 않은 나머지와 나눗셈 (임의의 기수에 의한)을 포함하기 때문에 더 복잡합니다. 나눗셈을하는 방법에 대한 좋은 생각이있을 때 이루어집니다. (여기서는 작은 (한 자리) 숫자로만 나누면됩니다. 일반 나누기보다 쉬울 수 있습니다.)
작은 숫자로 나누기
학교에서 나는 긴 나눗셈을 배웠다 . 다음은 독일에서 사용하는 표기법 (일반적으로 작성하지 않는 배경 계산에 대한 주석 포함)의 작은 (한 자리) 제수에 대한 예입니다.
12345 : 6 = 02057 1 / 6 = 0
-0┊┊┊┊ 0 * 6 = 0
──┊┊┊┊
12┊┊┊ 12 / 6 = 2
-12┊┊┊ 2 * 6 = 12
──┊┊┊
03┊┊ 3 / 6 = 0
- 0┊┊ 0 * 6 = 0
──┊┊
34┊ 34 / 6 = 5
-30┊ 5 * 6 = 30
──┊
45 45 / 6 = 7
-42 7 * 6 = 42
──
3 ==> quotient 2057, remainder 3.
우리는 이러한 제품 (0, 12, 0, 30, 42)을 계산하고 기본 나머지 연산이있는 경우 빼야 할 필요가 없습니다. 그러면 다음과 같이 보입니다 (물론 여기에서는 작업을 작성할 필요가 없습니다).
12345 : 6 = 02057 1 / 6 = 0, 1 % 6 = 1
12┊┊┊ 12 / 6 = 2, 12 % 6 = 0
03┊┊ 3 / 6 = 0, 3 % 6 = 3
34┊ 34 / 6 = 5, 34 % 6 = 4
45 45 / 6 = 7, 45 % 6 = 3
3
==> quotient 2057, remainder 3.
다른 형식으로 작성하면 이미 짧은 나눗셈 처럼 보입니다 .
우리는 다음을 관찰하고 증명할 수 있습니다.
첫 번째 숫자가 제수 d보다 작은 두 자리 숫자 x가 있으면 than x / d은 한 x % d자리 숫자이고 d보다 작은 한 자리 숫자이기도합니다. 이것은 귀납법과 함께 우리가 (나머지로) 두 자리 숫자를 제수로 나눌 필요가 있다는 것을 보여줍니다.
기수 BASE를 사용하여 큰 숫자로 돌아 오면 모든 두 자리 숫자는 Java로 표현할 수 있으며 long여기에는 네이티브 /및 %.
/**
* does one step in the short division algorithm, i.e. divides
* a two-digit number by a one-digit one.
*
* @param result the array to put the quotient digit in.
* @param resultIndex the index in the result array where
* the quotient digit should be put.
* @param divident the last digit of the divident.
* @param lastRemainder the first digit of the divident (being the
* remainder of the operation one digit to the left).
* This must be < divisor.
* @param divisor the divisor.
* @returns the remainder of the division operation.
*/
private int divideDigit(int[] result, int resultIndex,
int divident, int lastRemainder,
int divisor) {
assert divisor < BASE;
assert lastRemainder < divisor;
long ent = divident + (long)BASE * lastRemainder;
long quot = ent / divisor;
long rem = ent % divisor;
assert quot < BASE;
assert rem < divisor;
result[resultIndex] = (int)quot;
return (int)rem;
}
이제 루프에서이 메서드를 호출하여 항상 이전 호출의 결과를 lastRemainder.
/**
* The short division algorithm, like described in
* <a href="http://en.wikipedia.org/wiki/Short_division">Wikipedia's
* article <em>Short division</em></a>.
* @param result an array where we should put the quotient digits in.
* @param resultIndex the index in the array where the highest order digit
* should be put, the next digits will follow.
* @param divident the array with the divident's digits. (These will only
* be read, not written to.)
* @param dividentIndex the index in the divident array where we should
* start dividing. We will continue until the end of the array.
* @param divisor the divisor. This must be a number smaller than
* {@link #BASE}.
* @return the remainder, which will be a number smaller than
* {@code divisor}.
*/
private int divideDigits(int[] result, int resultIndex,
int[] divident, int dividentIndex,
int divisor) {
int remainder = 0;
for(; dividentIndex < divident.length; dividentIndex++, resultIndex++) {
remainder = divideDigit(result, resultIndex,
divident[dividentIndex],
remainder, divisor);
}
return remainder;
}
이 메서드는 여전히 나머지 int를 반환합니다.
이제 DecimalBigInt를 반환하는 공용 메서드를 원하므로 하나를 만듭니다. 인수를 확인하고, 작업 메서드에 대한 배열을 만들고, 나머지를 버리고, 결과에서 DecimalBigInt를 만드는 작업이 있습니다. (생성자는 거기에있을 수있는 선행 0을 제거합니다.)
/**
* Divides this number by a small number.
* @param divisor an integer with {@code 0 < divisor < BASE}.
* @return the integer part of the quotient, ignoring the remainder.
* @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
*/
public DecimalBigInt divideBy(int divisor)
{
if(divisor <= 0 || BASE <= divisor) {
throw new IllegalArgumentException("divisor " + divisor +
" out of range!");
}
int[] result = new int[digits.length];
divideDigits(result, 0,
digits, 0,
divisor);
return new DecimalBigInt(result);
}
대신 나머지를 반환하는 유사한 메서드도 있습니다.
/**
* Divides this number by a small number, returning the remainder.
* @param divisor an integer with {@code 0 < divisor < BASE}.
* @return the remainder from the division {@code this / divisor}.
* @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
*/
public int modulo(int divisor) {
if(divisor <= 0 || BASE <= divisor) {
throw new IllegalArgumentException("divisor " + divisor +
" out of range!");
}
int[] result = new int[digits.length];
return divideDigits(result, 0,
digits, 0,
divisor);
}
이러한 메서드는 다음과 같이 호출 할 수 있습니다.
DecimalBigInt d3_by_100 = d3.divideBy(100);
System.out.println("d3/100 = " + d3_by_100);
System.out.println("d3%100 = " + d3.modulo(100));
임의의 기수로 변환
이제 임의의 기수로 변환하는 기본 사항이 있습니다. 물론, 실제로 임의적 BASE이지는 않고 허용되는 것보다 작은 기수 만 있지만 이것은 너무 큰 문제는 아닙니다.
숫자 변환에 대한 다른 답변에서 이미 답변했듯이 "나누기, 나머지, 곱하기, 더하기"를 수행해야합니다. "곱하기 더하기"부분은 실제로 개별 숫자를 모으기 만하므로 간단한 배열로 대체 할 수 있습니다. 접속하다.
우리는 항상 몫과 나머지를 모두 필요, 우리는 대중 방법을 사용하지 않습니다 modulo하고 divideBy, 대신 반복적으로 호출 할 divideDigits방법을.
/**
* converts this number to an arbitrary radix.
* @param radix the target radix, {@code 1 < radix < BASE}.
* @return the digits of this number in the base-radix system,
* in big-endian order.
*/
public int[] convertTo(int radix)
{
if(radix <= 1 || BASE <= radix) {
throw new IllegalArgumentException("radix " + radix +
" out of range!");
}
첫째, 0에 대한 특수한 처리입니다.
// zero has no digits.
if(digits.length == 0)
return new int[0];
그런 다음 결과 숫자 (충분히 긴) 및 기타 변수에 대한 배열을 만듭니다.
// raw estimation how many output digits we will need.
// This is just enough in cases like BASE-1, and up to
// 30 digits (for base 2) too much for something like (1,0,0).
int len = (int) (Math.log(BASE) / Math.log(radix) * digits.length)+1;
int[] rDigits = new int[len];
int rIndex = len-1;
int[] current = digits;
int quotLen = digits.length;
quotLen마지막 몫의 자릿수 (선행 0 제외)입니다. 이것이 0이면 완료된 것입니다.
while(quotLen > 0) {
다음 몫에 대한 새 배열입니다.
int[] quot = new int[quotLen];
몫과 나머지 연산입니다. 몫은 이제에 quot있고 나머지는에 rem있습니다.
int rem = divideDigits(quot, 0,
current, current.length - quotLen,
radix);
나머지는 출력 배열에 넣습니다 (마지막 숫자에서 채움).
rDigits[rIndex] = rem;
rIndex --;
그런 다음 다음 라운드를 위해 어레이를 교체합니다.
current = quot;
몫에 선행 0이있는 경우 (기수가 BASE보다 작으므로 최대 1 개가 있음) 몫 크기를 1만큼 축소합니다. 다음 배열은 더 작아집니다.
if(current[0] == 0) {
// omit leading zeros in next round.
quotLen--;
}
}
루프 후에 rDigits 배열에 선행 0이있을 수 있으며이를 잘라냅니다.
// cut of leading zeros in rDigits:
while(rIndex < 0 || rDigits[rIndex] == 0) {
rIndex++;
}
return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}
그게 다야. 그래도 조금 복잡해 보입니다. 다음은 사용 방법의 예입니다.
System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
이러한 인쇄 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]하고 [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0], 그냥 같은 번호를 우리가 (하지만, 문자열에서) 전에 구문 분석한다.
이를 기반으로 문자열 형식을 지정할 수도 있습니다.
/**
* Converts the number to a String in a given radix.
* This uses {@link Character.digit} to convert each digit
* to one character.
* @param radix the radix to use, between {@link Character.MIN_RADIX}
* and {@link Character.MAX_RADIX}.
* @return a String containing the digits of this number in the
* specified radix, using '0' .. '9' and 'a' .. 'z' (as much as needed).
*/
public String toString(int radix) {
if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) {
throw new IllegalArgumentException("radix out of range: " + radix);
}
if(digits.length == 0)
return "0";
int[] rdigits = convertTo(radix);
StringBuilder b = new StringBuilder(rdigits.length);
for(int dig : rdigits) {
b.append(Character.forDigit(dig, radix));
}
return b.toString();
}
.NET Framework를 피하려는 경우 바이너리 코딩 십진수에 대한 라이브러리를 구현하거나 연구하고 싶을 수 있습니다 BigInteger. BigInteger그래도 사용하려면 90의 계승을 달성 할 수 있습니다 .
public static BigInteger factorial(BigInteger value) {
BigInteger total = BigInteger.ONE;
for (int i = 0; value.compareTo(BigInteger.ONE) == 1; i++) {
total = total.multiply(value);
value = value.subtract(BigInteger.ONE);
}
return total;
}
연산자를 사용하여 자바에서 산술 연산은 +, -, *, /, 및 %의 제약에 구속되는 자바 기본 데이터 형 .
당신의 범위에 원하는 숫자를 맞지 않는 경우를 말하는 것으로이 수단 double또는 long다음과 같은 내장 된 자바 (에 하나 같이 "큰 수"라이브러리를 사용해야합니다 BigDecimal를 , BigInteger의 ), 또는 타사 라이브러리를 사용하거나 직접 작성하십시오. 이는 또한 Java가 연산자 오버로딩을 지원하지 않기 때문에 산술 연산자를 사용할 수 없음을 의미합니다.
아래 코드를 사용하여 길이에 관계없이 숫자를 곱하십시오.
public class BigNumberMultiplication {
private static int[] firstBigNumber = null;
private static int[] secondBigNumber = null;
public static int[] baseMul(int[] baseMultiple, int base) {
System.out.println("baseMultiple" + Arrays.toString(baseMultiple) + base);
for (int i = 0; i < baseMultiple.length; i++) {
baseMultiple[i] *= base;
}
System.out.println("basemultipleresultwithoutcarryforward" + baseMultiple);
return carryForward(baseMultiple);
}
public static int[] basePowerMul(int[] basePowerMultiple, int base, int power) {
int basePowerMultipleTemp[] = baseMul(basePowerMultiple, base);
System.out.println("basePowerMultipleTemp" + Arrays.toString(basePowerMultipleTemp) + "power" + power);
int basePowerMultipleResult[] = new int[basePowerMultipleTemp.length + (power - 1)];
for(int i = 0; i < basePowerMultipleTemp.length; i++)
basePowerMultipleResult[i] = basePowerMultipleTemp[i];
if(power > 1){
for(int i = 0; i < (power - 1); i++)
basePowerMultipleResult[basePowerMultipleTemp.length + i] = 0;
}
System.out.println("basepowermulresult" + Arrays.toString(basePowerMultipleResult));
return basePowerMultipleResult;
}
public static int[] addBigNumber(int[] finalNumberInArray, int[] finalNumberInArrayTemp){
System.out.println("final number in array" + Arrays.toString(finalNumberInArray) + "finalNumberInTemp" + Arrays.toString(finalNumberInArrayTemp));
int n = finalNumberInArray.length;
for(int i = (finalNumberInArrayTemp.length - 1); i >= 0; i--){
finalNumberInArray[n - 1] += finalNumberInArrayTemp[i];
n--;
}
return carryForward(finalNumberInArray);
}
public static int[] carryForward(int[] arrayWithoutCarryForward){
int[] arrayWithCarryForward = null;
System.out.println("array without carry forward" + Arrays.toString(arrayWithoutCarryForward));
for (int i = arrayWithoutCarryForward.length - 1; i > 0; i--) {
if (arrayWithoutCarryForward[i] >= 10) {
int firstDigit = arrayWithoutCarryForward[i] % 10;
int secondDigit = arrayWithoutCarryForward[i] / 10;
arrayWithoutCarryForward[i] = firstDigit;
arrayWithoutCarryForward[i - 1] += secondDigit;
}
}
if(arrayWithoutCarryForward[0] >= 10){
arrayWithCarryForward = new int[arrayWithoutCarryForward.length + 1];
arrayWithCarryForward[0] = arrayWithoutCarryForward[0] / 10;
arrayWithCarryForward[1] = arrayWithoutCarryForward[0] % 10;
for(int i = 1; i < arrayWithoutCarryForward.length; i++)
arrayWithCarryForward[i + 1] = arrayWithoutCarryForward[i];
}
else{
arrayWithCarryForward = arrayWithoutCarryForward;
}
System.out.println("array with carry forward" + Arrays.toString(arrayWithCarryForward));
return arrayWithCarryForward;
}
public static int[] twoMuscularNumberMul(){
int finalNumberInArray[] = null;
for(int i = 0; i < secondBigNumber.length; i++){
if(secondBigNumber[i] == 0){}
else {
int[] finalNumberInArrayTemp = basePowerMul(Arrays.copyOf(firstBigNumber, firstBigNumber.length), secondBigNumber[i], secondBigNumber.length - i);
if(finalNumberInArray == null){
finalNumberInArray = finalNumberInArrayTemp;
System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
}
else{
finalNumberInArray = addBigNumber(finalNumberInArray, finalNumberInArrayTemp);
System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
}
}
}
return finalNumberInArray;
}
public static int [] readNumsFromCommandLine() {
Scanner s = new Scanner(System.in);
System.out.println("Please enter the number of digit");
int count = s.nextInt();
System.out.println("please enter the nuumber separated by space");
s.nextLine();
int [] numbers = new int[count];
Scanner numScanner = new Scanner(s.nextLine());
for (int i = 0; i < count; i++) {
if (numScanner.hasNextInt()) {
numbers[i] = numScanner.nextInt();
} else {
System.out.println("You didn't provide enough numbers");
break;
}
}
return numbers;
}
public static void main(String[] args) {
firstBigNumber = readNumsFromCommandLine();
secondBigNumber = readNumsFromCommandLine();
System.out.println("1st number" + Arrays.toString(firstBigNumber) + "2nd number" + Arrays.toString(secondBigNumber));
int[] finalArray = twoMuscularNumberMul();
System.out.println(Arrays.toString(finalArray));
}
}
강력한 텍스트 public class BigInteger {
public static String checkSignWithRelational(int bigInt1, int bigInt2){
if( bigInt1 < 0){
return "negative";
}else {
return "positive";
}
}
BigInteger( long init)
{
Long.parseLong(bigInt1);
}
BigInteger String (String init){
return null;
}
private static int intLenght(int bigInt) {
return Integer.toString(bigInt).length();
}
private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) {
int array[] = new int[arrayLength ];
for (int i = 0; i < arrayLength ; i++) {
array[i] = ( i<bigIntLength ?
getDigitAtIndex(bigInt, bigIntLength - i -1) :0 );
}
return array;
}
static String add(int bigInt1, int bigInt2) {
//Find array length
int length1 = intLenght(bigInt1);
int length2 = intLenght(bigInt2);
int arrayLength = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, arrayLength);
int array2[] = intToArray(bigInt2, length2, arrayLength);
return add(array1, array2);
}
private static String add(int[] array1, int[] array2) {
int carry=0;
int addArray[] = new int[array1.length + 1];
for (int i = 0; i < array1.length; i++) {
addArray[i] = (array1[i] + array2[i] + carry) % 10 ;
carry = (array1[i] + array2[i] + carry) / 10;
}
addArray[array1.length] = carry;
return arrayToString(addArray);
}
private static int getDigitAtIndex(int longint,int index){
return Integer.parseInt(Integer.toString(longint).substring(index, index+1));
}
private static String arrayToString(int[] addArray) {
String add = "";
boolean firstNonZero = false;
for (int i = addArray.length-1; i >= 0 ; i--) {
if(!firstNonZero && (addArray[i]==0)){
continue;
} else{
firstNonZero=true;
}
add += addArray[i];
if((i%3 ==0)&&i!=0){ add +=",";} //formatting
}
String sumStr = add.length()==0?"0":add;
return sumStr;
}
public static String sub(int bigInt1, int bigInt2) {
int length1 = intLenght(bigInt1);
int length2 = intLenght(bigInt2);
int arrayLength = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, arrayLength);
int array2[] = intToArray(bigInt2, length2, arrayLength);
return sub(array1, array2);
}
private static String sub(int[] array1, int[] array2) {
int carry=0;
int sub[] = new int[array1.length + 1];
for (int i = 0; i < array1.length; i++) {
sub[i] = (array1[i] - array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit
carry = (array1[i] - array2[i] + carry) / 10; //Compute carry
}
sub[array1.length] = carry;
return arrayToString(sub);
}
public static String mul(int bigInt1, int bigInt2) {
int length1 = intLenght(bigInt1), length2 = intLenght(bigInt2), length = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, length); int array2[] = intToArray(bigInt2, length2, length);
return mul(array1, array2);
}
private static String mul(int[] array1, int[] array2) {
int product[] = new int[array1.length + array2.length];
for(int i=0; i<array1.length; i++){
for(int j=0; j<array2.length; j++){
int prod = array1[i] * array2[j];
int prodLength = intLenght(prod);
int prodAsArray[] = intToArray(prod, prodLength, prodLength);
for (int k =0; k < prodAsArray.length; k++) {
product[i+j+k] += prodAsArray[k];
int currentValue = product[i+j+k];
if(currentValue>9){
product[i+j+k] = 0;
int curValueLength = intLenght(currentValue);
int curValueAsArray[] = intToArray(currentValue, curValueLength, curValueLength);
for (int l = 0; l < curValueAsArray.length; l++) {
product[i+j+k+l] += curValueAsArray[l];
}
}
}
}
}
return arrayToString(product);
}
public static int div(int bigInt1, int bigInt2) {
if ( bigInt2 == 0){
throw new ArithmeticException("Division by 0 is undefined:" + bigInt1+ "/" + bigInt2);
}
int sign = 1;
if(bigInt1 < 0) {
bigInt1 = -bigInt1;
sign = -sign;
}
if (bigInt2 < 0){
bigInt2 = -bigInt2;
sign = -sign;
}
int result =0;
while (bigInt1 >= 0){
bigInt1 -= bigInt2;
result++;
}
return (result - 1) * sign;
}
public static String check(String bigInt1, String bigInt2){
int difference;
StringBuilder first = new StringBuilder(bigInt1);
StringBuilder second = new StringBuilder(bigInt2);
if(bigInt1.length()> bigInt2.length()){
difference = bigInt1.length() - bigInt2.length();
for(int x = difference; x > 0; x--){
second.insert(0,"0");
}
bigInt2 = second.toString();
return bigInt2;
}else {
difference = bigInt2.length() - bigInt1.length();
for (int x = difference; x> 0; x--)
{
first.insert(0, "0");
}
bigInt1 = first.toString();
return bigInt1;
}
}
public static int mod(int bigInt1, int bigInt2){
int res = bigInt1 % bigInt2;
return (res);
}
public static void main(String[] args) {
int bigInt1 = Integer.parseInt("987888787");
int bigInt2 = Integer.parseInt("444234343");
System.out.println(bigInt1+" + "+bigInt2+" = "+add(bigInt1, bigInt2));
System.out.println(bigInt1+" - "+bigInt2+" = "+sub(bigInt1, bigInt2));
System.out.println(bigInt1+" * "+bigInt2+" = "+mul(bigInt1, bigInt2));
System.out.println(bigInt1+" / "+bigInt2+" = "+div(bigInt1, bigInt2));
System.out.println(bigInt1+" % "+bigInt2+" = "+mod(bigInt1, bigInt2));
}
}
90을하고 싶을 때! 또는 다른 대규모 계산을 시도하고 각 요소가 숫자 중 하나를 보유하는 int [] 배열을 사용합니다. 그런 다음 다른 int [] 배열에서 답을 얻기 위해 펜과 종이를 사용하는 전통적인 곱셈을 적용합니다.
이것은 내가 100을 계산하는 Java로 작성한 코드입니다! 오히려 빨리. 원하는대로 자유롭게 사용하십시오.
public int factoial(int num) {
int sum = 0;
int[][] dig = new int[3][160];
dig[0][0] = 0;
dig[0][1] = 0;
dig[0][2] = 1;
for (int i = 99; i > 1; i--) {
int len = length(i);
for (int k = 1; k <= len; k++) { // Sets up multiplication
int pos = len - k;
dig[1][pos] = ((i / (int) (Math.pow(10, pos))) % 10);
}
int temp;
for (int k = 0; k < len; k++) { // multiplication
for (int j = 0; j < 159; j++) {
dig[2][k + j] += (dig[1][k] * dig[0][j]);
if (dig[2][k + j] >= 10) {
dig[2][k + j + 1] += dig[2][k + j] / 10;
dig[2][k + j] = dig[2][k + j] % 10;
}
}
}
sum = 0;
for (int k = 159; k >= 0; k--) {
System.out.print(dig[2][k]);
dig[0][k] = dig[2][k];
dig[1][k] = 0;
sum += dig[2][k];
dig[2][k] = 0;
}
System.out.println();
}
return sum;
}
우리가 산술 연산을 수행하려는 정말 큰 숫자가 문자열과 같은 어떤 객체 형식이어야하는 것보다 크다면.
문자 길이가 BigInteger 범위보다 큰 문자열이되도록하십시오.
이 경우 노트북에서 수행하는 방식으로 산술 연산을 수행합니다. 예를 들어-덧셈을해야한다고 가정 해 봅시다. 길이에 대해 두 문자열을 비교하는 것으로 시작하십시오. 세 개의 새로운 문자열을 만드십시오. 첫 번째 문자열은 더 작은 문자열입니다. 두 번째 문자열은 길이가 작은 문자열과 동일한 긴 문자열의 맨 오른쪽 부분 문자열입니다. 세 번째 문자열은 왼쪽에서 남은 긴 문자열입니다. 이제 문자를 한 번에 한 문자 씩 정수로 변환하고 int 변수에 캐리를 유지하는 끝에서 첫 번째와 두 번째 문자열을 추가합니다. 각 추가 직후에 합계를 StringBuffer에 추가하십시오. 두 줄을 추가 한 후 세 번째 줄에 대해 동일한 작업을 수행하고 계속 캐리를 추가합니다. 결국 StringBuffer를 뒤집고 String을 반환합니다.
덧셈에 사용한 코드는 다음과 같습니다.
public String addNumber(String input1,String input2){
int n=0;String tempStr;
String one="";
String two="";
if(input1.length()>input2.length()){
n=input1.length()-input2.length();
tempStr=new String(input1);
one=new String(input1.substring(n,input1.length()));
two=new String(input2);
}else{
n=input2.length()-input1.length();
tempStr=new String(input2);
one=new String(input2.substring(n,input2.length()));
two=new String(input1);
}
StringBuffer temp=new StringBuffer();
for(int i=0;i<n;i++){
temp.append(tempStr.charAt(i));
}
StringBuffer newBuf=new StringBuffer();
int carry=0;
int c;
for(int i=one.length()-1;i>=0;i--){
int a=Character.getNumericValue(one.charAt(i));
int b=Character.getNumericValue(two.charAt(i));
c=a+b+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
String news=new String(temp);
for(int i=news.length()-1;i>=0;i--){
c=(Character.getNumericValue(news.charAt(i)))+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
if(carry==1){
newBuf.append(""+carry);
}
String newisis=new String(newBuf.reverse());
return newisis;
}
'Programing' 카테고리의 다른 글
| contenteditable의 자리 표시 자-포커스 이벤트 문제 (0) | 2020.11.29 |
|---|---|
| Linux / unix에서 ini / config 파일의 위치? (0) | 2020.11.29 |
| iOS에서 UISearchBar 구성 요소의 배경색을 변경하는 방법 (0) | 2020.11.29 |
| 자바, 두 날짜 사이의 일 수 계산 (0) | 2020.11.29 |
| 수평 로딩 진행률 표시 줄을 만드는 방법은 무엇입니까? (0) | 2020.11.29 |