再帰的な累乗法を固定しますか？

Question

私は現在、再帰を使用して累乗計算を行う方法に取り組んでいます。これまで私が持っているものは次のとおりです。

public static long exponentiation(long x, int n) { 

    if (n == 0) { 
     return 1; 
    } else if (n == 1) { 
     return x; 
     // i know this doesn't work since im returning long 
    } else if (n < 0) { 
     return (1/exponentiation(x, -n)); 
    } else { 
     //do if exponent is even 
     if (n % 2 == 0) { 
      return (exponentiation(x * x, n/2)); 
     } else { 
      // do if exponent is odd 
      return x * exponentiation(x, n - 1); 
     } 
    } 
} 

私には2つの問題があります。最初の問題は、負の指数を行うことができないということです。負の指数を必要としないので、これは大きな問題ではありません。第二の問題は、私に間違った答えを与える特定の計算です。例えば2^63は私に正しい値を与えますが、それは私に負の数を与えます。そして2^64そしてちょうど私に0を与えてください。私はこれを修正するためにとにかくありますか？私はlongをdoubleに切り替えることができ、私の方法は完全に機能することを知っています。しかし、私の教授はlongを使用する必要があります。ご協力ありがとうございました！

Answer 1

longが表すことができる最大値は2^63 -1です。したがって、2^63を計算すると、それは長いものが保持してラップできるものよりも大きくなります。ロングはtwos-complementを使用して表されます。

longをdoubleに変更するだけでは正しく動作しません。メソッドのセマンティクスを変更します。浮動小数点数には制限があります。 64ビット浮動小数点数では、64ビット整数と同じ数の数値しか表現できません。彼らはちょうど異なって配布されています。 longは-2^63と2^63-1のすべての整数を表すことができます。倍数は数の分数を表すこともできますが、高い数字ではすべての数字を表すことさえできません。

たとえば、あなたが100000000000000000000000000000000000000000000000000後に表すことができ、次のダブルは100000000000000030000000000000000000000000000000000ある - ので、あなたは、二重に表現できないなんと30000000000000000000000000000000000をmissiongています。

あなたは修正するのを嫌うものを修正しようとしています。 longを使用すると、メソッドが返す固定の最大戻り値があります。オーバーフローした場合の処理​​方法を明確に記述し、そのようなオーバーフローを処理したい場合があります（例えばMath#multiplyExactlyを使用します）。しかし、返さなければならない戻り値が長い場合は、それを使用する必要があります。

Answer 2

longの配列で結果を保持できます。result[]としましょう。まず、ロジックをresult[0]に適用します。しかし、その値が負になるときは、result[1]を1増分だけインクリメントしてください。

1） 2）今、あなたのロジックは非常に厄介になり、私は自分の電話に入力しているので、この部分は読者のための練習として残されています。 3）result[1]がオーバーフローすると、result[2]...

結果を印刷すると、結果が再び乱雑になります。

これは、BigIntegerがどのように機能するか（多かれ少なかれ）ですか？私はそのコードを見たことがない、あなたがしたいかもしれない。

しかし、基本的に、ポリゴンは正しいです。相当な回避策がなければ、上限があります。