在不使用BigInteger的情况下处理Java中的大整数 [英] Handling large integers in Java without using BigInteger

问题描述

我目前正在从事一项任务，该任务涉及使用线性时间复杂度算法来计算高达F(300)的斐波那契数.通过快速搜索，我知道Java long将在F(93)处溢出，因此我试图弄清楚如何存储这么大的数字.

I am currently working on an assignment that involves calculating Fibonacci numbers up to F(300) using a linear time complexity algorithm. I know via a quick search that a Java long will overflow at around F(93), so I am trying to figure out how to store such a large number.

但是，我们的作业指出不允许我们使用BigInteger之类的语言库来存储我们的数字.我们必须编写自己的大整数数据类型或对象.

However, our assignment states that we are not allowed to use language libraries such as BigInteger to store our numbers. We must write our own large integer data type or object.

在这种情况下，我该怎么办?我从来没有写过自己的数据类型来处理类似大整数的事情.有一些常用的方法吗?

What exactly am I to do in this case? I have never before had to write my own data type to handle something like a large integer. Is there some usual method of doing this?

推荐答案

我相信您需要从原始数组中创建数据类型，例如int []或long []，以便将结果值逐位存储此数组的元素. 就像您可以使用两个int来存储long的位一样，您也需要花费更多的int来存储更长的数字.

I believe what you need is to create a data type out of primitive arrays, like int[] or long[] so that you store result value by bits across elements of this array. Just like you can use two int's to store a long's bits you make take more ints to store a longer number.

但是，一个问题是解释该值，例如，您希望打印该值-如果像2 ^ n1 + 2 ^ n2 + ... + 2 ^ nk这样的字符串是单独的，则需要一个算法不可接受.

One problem though is to interpret this value, say, you wish to print the value - that would require an algorithm on its own, if a string like 2^n1 + 2^n2 + ... + 2^nk is not acceptable.

一个示例(使用字节数组存储十进制数字):

An example (using byte array to store decimal digits):

import java.util.ArrayList;
import java.util.List;


public final class HumongousInt {
public static HumongousInt of( String string ) {
    return new HumongousInt( asByteArray( string ) );
}

private static byte[] asByteArray( String string ) {
    int length = string.length();
    byte[] data = new byte[ length ];
    for( int i = 0; i < length; i++ ) {
        data[ i ] = asByte( string.charAt( i ) );
    }
    return data;
}

private static byte asByte( char c ) {
    if( c > '9' && c < '0' ) {
        throw new IllegalArgumentException( "Wrong numbe format only numbers 0-9 could be present" );
    }
    return ( byte ) ( c - '0' );
}

private final byte[] digits;

private HumongousInt( byte[] digits ) {
    this.digits = digits;
}

public HumongousInt add( HumongousInt other ) {
    int maxLength = Math.max( this.digits.length, other.digits.length );
    ArrayList< Byte > data = new ArrayList<>();
    int overhead = 0;
    int i = 1;
    while( overhead > 0 || ( i <= maxLength ) ) {
        int currentDigit = overhead;
        int thisIndex = ( this.digits.length - i );
        if( thisIndex >= 0 ) {
            currentDigit += this.digits[ thisIndex ];
        }
        int otherIndex = ( other.digits.length - i );
        if( otherIndex >= 0 ) {
            currentDigit += other.digits[ otherIndex ];
        }
        overhead = currentDigit / 10;
        data.add( Byte.valueOf( ( byte ) ( currentDigit %= 10 ) ) );
        i++;
    }
    return new HumongousInt( asInvertedByteArray( data ) );
}

private byte[] asInvertedByteArray( List< Byte > list ) {
    byte[] data = new byte[ list.size() ];
    for( int i = data.length - 1, j = 0; i >= 0; i--, j++ ) {
        data[ j ] = list.get( i );
    }
    return data;
}

public HumongousInt add( int i ) {
    return add( HumongousInt.of( Integer.toString( i ) ) );
}

@Override
public String toString() {
    StringBuilder builder = new StringBuilder( digits.length );
    for( byte b : digits ) {
        builder.append( b );
    }
    return ( digits[ 0 ] == ( byte ) 0 ) ? builder.substring( 1 ) : builder.toString();
}
}

这篇关于在不使用BigInteger的情况下处理Java中的大整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！