BigIntegerを使用せずにカラツバアルゴリズムをJavaで実装しようとしています。私のコードは、両方の整数が同じで桁数が同じ場合にのみ適用されます。正しい答えは得られませんが、正しい答えにかなり近い答えが得られます。たとえば、12*12 の場合は 149 になります。私は自分のコードの何が問題なのかを理解できません。なぜなら、私は（本によって）すべてを正しく行ったと信じているからです。これが私のコードです。
public static void main(String[] args) {
long ans=karatsuba(12,12);
System.out.println(ans);
}
private static long karatsuba(long i, long j) {
if (i<10 || j<10){
return i*j;
}
int n=getCount(i);
long a=(long) (i/Math.pow(10, n/2));
long b=(long) (i%Math.pow(10, n/2));
long c=(long) (j/Math.pow(10, n/2));
long d=(long) (j%Math.pow(10, n/2));
long first=karatsuba(a,c);
long second=karatsuba(b,d);
long third=karatsuba(a+b,c+d);
return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10,n/2))+third));
}
private static int getCount(long i) {
String totalN=Long.toString(i);
return totalN.length();
}
編集：
Ziyao Wei のおかげで、問題は「3 番目」を「2 番目」に置き換えることでした。ただし、現在別の問題があります。
からつば(1234,5678)を呼ぶと正解が出ますが、からつば(5678,1234)を呼ぶと正解が出ません。誰かがその理由を知っている可能性がありますか？私の更新されたコードは次のとおりです。
public static void main(String[] args) {
//wrong answer
long ans=karatsuba(5678,1234);
System.out.println(ans);
//correct answer
long ans1=karatsuba(1234,5678);
System.out.println(ans1);
}
private static long karatsuba(long i, long j) {
if (i<10 || j<10){
return i*j;
}
int n=getCount(i);
long a=(long) (i/Math.pow(10, n/2));
long b=(long) (i%Math.pow(10, n/2));
long c=(long) (j/Math.pow(10, n/2));
long d=(long) (j%Math.pow(10, n/2));
long first=karatsuba(a,c);
long second=karatsuba(b,d);
long third=karatsuba(a+b,c+d);
return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10, n/2))+second));
}
アップデート：
「n/2」の値を切り上げることができたので、問題は解決しましたが、4 桁を超える数字を使用するとバグが発生します。これが私の更新されたコードです：
public static void main(String[] args) {
System.out.println(Math.round(5.00/2));
//correct answer
long ans=karatsuba(5678,1234);
System.out.println(ans);
//correct answer
long ans1=karatsuba(1234,5678);
System.out.println(ans1);
//wrong answer
long ans2=karatsuba(102456,102465);
System.out.println(ans2);
}
private static long karatsuba(long i, long j) {
if (i<10 || j<10){
return i*j;
}
double n=Math.round(getCount(i));
long a=(long) (i/Math.pow(10, Math.round(n/2)));
long b=(long) (i%Math.pow(10, Math.round(n/2)));
long c=(long) (j/Math.pow(10, Math.round(n/2)));
long d=(long) (j%Math.pow(10, Math.round(n/2)));
long first=karatsuba(a,c);
long second=karatsuba(b,d);
long third=karatsuba(a+b,c+d);
return ((long) ((first*Math.pow(10, Math.round(n)))+((third-second-first)*Math.pow(10, Math.round(n/2)))+second));
}
private static double getCount(long i) {
String totalN=Long.toString(i);
return totalN.length();
}
BigInteger を使用せずに、より大きな数 (4 桁以上) の解決策を誰かが思いついた場合は、お知らせください。ありがとう。