2

BigInteger メソッドを使用せずに非常に大きな数を計算するために、このプログラムを作成しました。私はそれを終え、それは正常に動作しています。私は StringBuilder と多くの parseInt 呼び出しを使用してそれを完了しました。これを行うより効率的な方法はありますか？

ちなみに、これは単なるワークシートです。悪いプログラミング スタイルは無視してください。仕事が終わったら、それを再編成します。

private String add (String x, String y)
{
    String g = "";
    StringBuilder str = new StringBuilder();
    int sum;
    double atHand = 0;
    int dif = (int)(Math.abs(x.length()-y.length())); 

    if(x.length() >= y.length())   //adding zero for equalise number of digits.
    {
        for(int i = 0; i<dif; i++)
            g += "0";
        y = g+y;    
    }
    else 
    {
        for(int i = 0; i<dif; i++)
            g += "0";
        x = g + x;
    }

    for (int i = y.length()-1; i >=0 ; i--)
    {
        sum = Integer.parseInt(x.substring(i, i+1)) +Integer.parseInt(y.substring(i,i+1)) + (int)atHand; 

        if(sum<10) 
        {
            str.insert(0, Integer.toString(sum)); 
            atHand = 0;  
        }else
        {
            if(i==0)
                str.insert(0, Integer.toString(sum)); 
            else
            {
                atHand = sum *0.1;
                sum = sum %10;  
                str.insert(0, Integer.toString(sum));
            }
        }
    }
    return str.toString();
}
4

1 に答える 1

3

文字ごとに行うのではなく、一度に文字を取得kして、Javaintまたはlong. 「ブロック」と、実装に応じてオーバーフロー (つまり、そのようなもの(threshold * 2) < positive_type_limit) の両方を保持できる所定のしきい値を使用します。簡単にするために、10 の累乗であるしきい値を使用して、10 進数の文字列表現の文字に直接マップできるようにします (たとえば、オーバーフローしきい値が 100 万の場合、6 文字を取ることができます)。 a time) - これには、効率的に文字列に変換できるという追加の利点もあります。

次に、「ブロック」ははるかに大きくなります。次に、これらのブロックと制限/しきい値 (使用する整数プリミティブ型に基づく) を使用して、オーバーフローを追加して実行します。したがって、基本的にはの配列で操作していますints。

時間の計算量は のままですO(n)が、より小さくなりますn(より具体的にO(n/k)はk、 は 1 つのブロックが表す 10 進数の桁数になります)。

すべてのソリューションには、大きな数を小さなブロックに分割して操作することが含まれると思います。あなたはすでにこれを行っています.あなたの現在の解決策はblocksize=k=1.

ブロックを最大限に活用するには、制限として 2 の累乗を使用できます。たとえば、32 ビットの符号なし整数型の場合、しきい値を に設定します2^31(または 2^32 に設定することもできますが、場所と場所によって異なります)。オーバーフローを格納して次の要素に渡す方法)。

BigInteger が同様の手法を使用していても驚かないでしょう。

于 2012-06-07T14:27:30.127 に答える