Stack Overflow
Stack Overflow

Questions tagged [karatsuba]

Asymptotically fast multiplication algorithm for big integers. Understanding this algorithm and its implementations.

Karatsuba algorithm requires O(nlog₂3) single digit multiplication operations to multiply a pair of n-digit numbers and is therefore asymptotically faster than the common O(n²) multiplication algorithm.

It was proposed by Anatoly Karatsuba in a paper published in the Proceedings of the USSR Academy of Science in 1962.

A related tag is that covers both Schönhage–Strassen multiplication algorithm and Strassen matrix multiplication algorithm.

Useful links

92 questions
4
votes
8 answers

Karatsuba Multiplication Implementation

I recently implemented Karatsuba Multiplication as a personal exercise. I wrote my implementation in Python following the pseudocode provided on wikipedia: procedure karatsuba(num1, num2) if (num1 < 10) or (num2 < 10) return num1*num2 /*…
Solomon Bothwell
  • 1,004
  • 2
  • 12
  • 21
4
votes
2 answers

Product of two complex numbers in less than 3 multiplications

Can someone break this down for me? Why can't it be done in two multiplications? The Multiplication of Complex Numbers If the number of multiplications required for a computation is regarded as a measure of its difficulty and these computations are…
SuperCell
  • 241
  • 1
  • 12
3
votes
0 answers

How to implement iterative Karatsuba efficiently and nontrivially?

Is there any efficient C/C++ implementation or algorithm descritpion for iterative Karatsuba w/o using stack/queue to simulate the function stack in recursive Karatsuba? Suppose F x G = (F_1 + F_2 x^n) x (G_1 + G_2 x^n), where F and G are…
Leo
  • 61
  • 3
3
votes
1 answer

How to compute the running time of Karatsuba Algorithm?

I know that the formula is T(n)=3T(n/2)+O(n), and using the master method I can get the T(n)=n^(log3) with 2 being the base. But I still don't know how to get the answer without using master method. Because the result I get from the recursive…
Zoe Lee
  • 143
  • 5
2
votes
0 answers

Karatsuba Implementation Issues

Couple things: I am a university student This is not a homework problem (I'm curious about how bignum libraries work) All the code snippets here can be compiled with gcc -lgmp Here is my implementation which keeps returning incorrect answers. I've…
Lev Knoblock
  • 611
  • 2
  • 6
  • 20
2
votes
3 answers

the implementation of the Karatsuba algorithm, the method only counts the small numbers true, but the big answer is not correct, what's the problem?

The implementation of the Karatsuba algorithm, the method only counts the small numbers true, but the big answer is not correct, what's the problem? var x = "1685287499328328297814655639278583667919355849391453456921116729"; var y =…
Serhiy Ivanchenko
  • 31
  • 3
2
votes
1 answer

I want to implement Karatsuba Multiplication in python

I want to implemented Karatsuba Multiplication in python. But I get the right answer when the number is large. Can anyone tell me where my code is wrong？ Karatsuba Multiplication Implementation is not right when x is very large. import math def…
ken
  • 35
  • 1
  • 7
2
votes
1 answer

How would you n where one algorithm is preferred over another algorithm

I'm trying to compare two algorithms and their Big Oh efficiencies. I am trying to find the value for n where one algorithm becomes more efficient than the other algorithm. Any helpful examples or resources would be a huge help.
Patrick Hession
  • 45
  • 6
2
votes
0 answers

What is wrong with this Karatsuba Multiplication Algorithm Implementation?

First things first: ~ This is my first question on StackOverflow. ~ I am a university student. ~ This is not my homework problem (I am doing this to increase my algorithmic thinking). Here is my implementation, which keeps on returning wrong…
Shikhar Jaiswal
  • 125
  • 8
2
votes
1 answer

Karatsuba Integer Multiplication failing with segmentation fault

As I run the program, it crashes with segmentation fault. Also, when I debug the code in codeblocks IDE, I am unable to debug it as well. The program crashes even before debugging begins. I am not able to understand the problem. Any help would be…
RK21
  • 21
  • 3
2
votes
1 answer

Error Implementing the karatsuba algorithm with BigInteger

I am trying to implement the karatsuba algorithm with Java suing BigInteger, I followed all the steps, but I am not getting the correct result, what is making me crazy. Here is my code: public BigInteger karatsuba(BigInteger a, BigInteger b, int…
shadow
  • 43
  • 5
2
votes
2 answers

Multiplication of 2 64-digit numbers in C++

I have karatsuba multiplication algorithm implemented. I want to improve it in this way that I can multiply 2 64-digit numbers but I don't know how to do this. I was given a hint that both numbers contain number of digits that is a power of two but…
user7120361
2
votes
1 answer

Why isn't the complexity of karatsuba O(n^2)?

import java.math.BigInteger; import java.util.Random; class Karatsuba { private final static BigInteger ZERO = new BigInteger("0"); public static BigInteger karatsuba(BigInteger x, BigInteger y) { // cutoff to brute force int N =…
Ambikeya Singh Sangwan
  • 65
  • 1
  • 9
1
vote
1 answer

Why (10^n/2) * a + b is a recursive algorithm?

I'm currently reading a book called Algorithms Illuminated Part 1: Basics and came across a bit discussing about Karatsuba Multiplication. The example says "a number x with an even number n of digits can be expressed in terms of two n/2-digit…
mrRobot9
  • 15
  • 5
1
vote
1 answer

Karatsuba algorithm, slight inaccuracy

I've spent a while trying to implement Karatsuba's algorithm in Python and I'm getting close though when I try to multiply two larger numbers (over ~10^15), my result starts to get inaccurate. I can't figure out why. Side question: Would there be a…
tim_76
  • 74
  • 6
1
2 3 4 5 6 7