The Karatsuba test

[lehs]

The idea of Karatsuba multiplication is to reduce 4 multiplications to 3.
Suppose X=X0+X1*C^m and Y=Y0+Y1*C^m, where C=2^n and X0,X1,Y0,Y1<C^m.
Then Z=X*Y=(X0+X1*C^m)(Y0+Y1*C^m)=Z0+Z1*C^m+Z2*C^2m, where
Z0=X0*Y0
Z1=X0*Y1+X1*Y0
Z2=X1*Y1
It takes 4 multiplications to get Z as above, but
Z1=(X0+X1)(Y0+Y1)-Z0-Z2, which reduce the number of multiplications by one.
Obviously this wouldn't do single cell multiplication faster. The cost to find m,X0,X1,Y0,Y1,Z0,Z1,Z2 and finally Z would be to high.

I've implemented a preliminary Karatsuba multiplication in biginteger for GForth.
For the Android straight multiplication become much faster:

figures quote
100 8
1000 6.5
10000 2.5
20000 2

Multiplication of two 20000 figures numbers take 0.75 seconds straight and 1.4 seconds with Karatsuba.
My biginteger works very simple and there are too much copying in this case, even though I use
C=2^32 and get X0,X1,Y0,Y1 by redirecting pointers. But there are to much juggling to make the calculations efficient enough. In biginteger all calculations are done with the top elements on the stack, which is perfect in normal case. But perhaps it's a good idea to define alternative operations, that create the answer on top of stack but read cells from big numbers at specified addresses. That would decrease the juggling.
And maybe make Karatsuba multiplication as fast as straight multiplication? :)

Are there really any efficient high level implementations of Karatsuba multiplication?

[lehs]

In this implementation I doubt that Karatsuba ever is faster than Straight in non compiled code, but in optimized SP-Forth there is a break-point for numbers with about 70000 figures (3.1 seconds).

[Andrew Haley]

lehs <skydda...@gmail.com> wrote:

> And maybe make Karatsuba multiplication as fast as straight multiplication? :)
>
> Are there really any efficient high level implementations of
> Karatsuba multiplication?

Java uses the algorithm here for everything larger than 80 32-bit digits:
hg.openjdk.java.net/jdk9/jdk9/jdk/file/2d94659f7ff3/src/java.base/share/classes/java/math/BigInteger.java

Andrew.

[lehs]

But I'm pretty sure that their implementation is coded in assembler. I'm trying to do an ANS Forth implementation. What I've seen of high level implementations so far I doubt they are faster.

[Andrew Haley]

lehs <skydda...@gmail.com> wrote:

> Den l?rdag 27 maj 2017 kl. 08:33:28 UTC+2 skrev Andrew Haley:
>> lehs <skydda...@gmail.com> wrote:
>>
>> > And maybe make Karatsuba multiplication as fast as straight multiplication? :)
>> >
>> > Are there really any efficient high level implementations of
>> > Karatsuba multiplication?
>>
>> Java uses the algorithm here for everything larger than 80 32-bit digits:
>> hg.openjdk.java.net/jdk9/jdk9/jdk/file/2d94659f7ff3/src/java.base/share/classes/java/math/BigInteger.java
>

> But I'm pretty sure that their implementation is coded in assembler.

I'm pretty sure the implementation is there in Java, right in front of
your nose! It starts at line 1273. But the speedup ratio shouldn't
matter whether it's written in a high-level language or not.

Andrew.

[lehs]

Yes I saw that, but it's compiled code using optimized procedures. This proves that my approach to big integers isn't at all efficient for very big integers. I have to complement with some non copying routines like

b@+ \ ad1 n1 ad2 n2 -- big

that never copies big numbers.

[lehs]

No, there was a bug so the recursion had to fight to reach the terminal case. Without any other changes the threes-hold is now around 1500 figures on SP-Forth.

[Robert L.]

On 5/26/2017, lehs wrote:

> Z would be to high

In Enlish:

Z would be too high

--
In Stockholm ... 20 Muslim men ... began to assault the children, ripping their
swimsuits off and beating the boys when they tried to stop the assault....
[T]he men cornered one of the [11-year-old] girls in a grotto in the bathhouse
and gang raped her. The police refused to press any charges.
http://www.liveleak.com/view?i=807_1369627137

[lehs]

Right, in English.

[Paul Rubin]

lehs <skydda...@gmail.com> writes:
> No, there was a bug so the recursion had to fight to reach the
> terminal case. Without any other changes the threes-hold is now around
> 1500 figures on SP-Forth.

I think GMP also switches somewhere in that ballpark. I wonder how
hard it is to implement Toom-Cook for even bigger numbers.

[lehs]

I think Toom-Cook is too much for me and for my bigintegers.

Karatsuba seems to be very dependent of the terminal case. If splitting down to singles handled with UM* the threes-hold is high. But if simple multiplication is that competeable why not use it in the terminal case on an earlier stage - and get a lower threes-hold?

In bigintegers there is an improvement of speed with a factor of about 1.25 for 2048-bit numbers when terminating with ordinary b* as soon as the greatest multiplicand is less than about 1200 bit long.

It seems that the terminal condition is rather important and that it not only is a question of how big the multiplicands are.

[Albert van der Horst]

In article <87k252p...@nightsong.com>,

I implemented Toom-Cook once in C. It was not very hard.
I was very disappointed with the speedup I got for the effort.
That was on a VAX with a 100 Kflop processor, 1992 ish.

(For those not in the know Toom-Cook can be found in Knuth TAO
and is a generalisation of 3 mult's instead of 4 trick. )

Groetjes Albert
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[foxaudio...@gmail.com]

On Saturday, May 27, 2017 at 8:08:53 AM UTC-4, Robert L. wrote:
> On 5/26/2017, lehs wrote:
>
> > Z would be to high
>
> In Enlish:
>
> Z would be too high
>
> --

That was pretty funny Robert. It appears that Enlish [sic] is hard
too [sic] get right even for native speakers.

[Raimond Dragomir]

I think every language is hard too get it rite for native speakers...

[Rudy Velthuis]

lehs wrote:

> Are there really any efficient high level implementations of
> Karatsuba multiplication?

I don't know any in Forth, but I certainly know a few in other
languages, including in my own BigInteger for Delphi. The norm for
multi-precision implementations, GMP (GNU Multi-Precision library) uses
it too. So does Java's BigInteger. And it does make a difference, but
only above a certain threshold (size of the multiplicands). This
threshold is generally found empirically, and differs from
implementation to implementation (and also on different platforms,
etc.).

--
Rudy Velthuis http://www.rvelthuis.de

"He who fights with monsters might take care lest he thereby
become a monster. For if you gaze for long into an abyss, the
abyss gazes also into you."
-- Nietzsche

[Rudy Velthuis]

lehs wrote:

> > Java uses the algorithm here for everything larger than 80 32-bit
> > digits:
> > hg.openjdk.java.net/jdk9/jdk9/jdk/file/2d94659f7ff3/src/java.base/sh
> > are/classes/java/math/BigInteger.java
> >
> > Andrew.
>
> But I'm pretty sure that their implementation is coded in assembler.

No, it isn't. The sources are available in the SDK. Plain Java. Take a
look at java.math.

--
Rudy Velthuis http://www.rvelthuis.de

"We first fought... in the name of religion, then Communism, and
now in the name of drugs and terrorism. Our excuses for global
domination always change." -- Serj Tankian

[Rudy Velthuis]

Albert van der Horst wrote:

> In article <87k252p...@nightsong.com>,
> Paul Rubin <no.e...@nospam.invalid> wrote:
> >lehs <skydda...@gmail.com> writes:
> >> No, there was a bug so the recursion had to fight to reach the
> >> terminal case. Without any other changes the threes-hold is now
> around >> 1500 figures on SP-Forth.
> >
> > I think GMP also switches somewhere in that ballpark. I wonder how
> > hard it is to implement Toom-Cook for even bigger numbers.
>
> I implemented Toom-Cook once in C.

It is not very hard indeed. The book by, IIRC, Bradley and Zimmerman
makes it pretty easy. But which one? There are several ones, 3-way,
4-way, mixed ones, etc., optimized (but GPL-ed) ones, etc. B&Z
describes only 3-way, IIRC.

--
Rudy Velthuis http://www.rvelthuis.de

"The only one listening to both sides of an argument
is the neighbor in the next apartment" -- unknown