L'implémentation de l'algorithme Karatsuba, la méthode ne compte que les petits nombres vrais, mais la grande réponse n'est pas correcte, quel est le problème?
var x = "1685287499328328297814655639278583667919355849391453456921116729";
var y = "7114192848577754587969744626558571536728983167954552999895348492";
function karatsuba(x, y) {
if (x.length < 2 && y.length < 2) {
return BigInt(parseInt(x) * parseInt(y));
}
var m = Math.min(x.length, y.length);
var m2 = m / 2;
var a = BigInt(x.substring(0, m2));
var b = BigInt(x.substring(m2));
var c = BigInt(y.substring(0, m2));
var d = BigInt(y.substring(m2));
var ac = a * c;
var bd = b * d;
var sum = (a + b) * (c + d) - ac - bd;
return BigInt(Math.pow(10, m)) * ac + BigInt(Math.pow(10, m2)) * sum + bd;
}
console.log(karatsuba(x, y));
3 Réponses :
L'appel de Math.pow est très suspect. Selon la documentation , il
Renvoie une approximation dépendant de l'implémentation du résultat de l'augmentation de x à la puissance y.
Vous ne voulez aucune approximation en Karatzuba.
Vous utilisez m2 pour diviser les nombres, mais m (aussi) pour mettre à l'échelle avant / en combinaison / "(polynomial) evaluation".
Vous devez utiliser
2 * m2.
return BigInt(parseInt(x) * parseInt(y)); It defeats the point to multiply large things together before constructing a BigInt.
(Je pense que je vois votre point, mais le code cité est utilisé lorsque les deux facteurs sont plus courts que deux chiffres (pas grand par mon livre). Mais alors, il y a mise à l'échelle en utilisant le * < / code> opérateur…)
Bienvenue dans StackOverflow! Veuillez ajouter votre code réel à la question plutôt qu'une capture d'écran de votre code. Je vous remercie!