Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #59885 > unrolled thread

The Karatsuba test

Back to article view | Back to comp.lang.forth

Contents

  The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-26 14:36 -0700
    Re: The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-26 23:23 -0700
    Re: The Karatsuba test Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-05-27 01:33 -0500
      Re: The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-26 23:45 -0700
        Re: The Karatsuba test Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-05-27 01:51 -0500
          Re: The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-27 00:07 -0700
            Re: The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-27 01:43 -0700
              Re: The Karatsuba test Paul Rubin <no.email@nospam.invalid> - 2017-05-27 11:34 -0700
                Re: The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-27 20:43 -0700
                Re: The Karatsuba test albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-05-28 09:51 +0200
                  Re: The Karatsuba test "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-06-02 00:53 +0000
        Re: The Karatsuba test "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-06-02 00:50 +0000
    Re: The Karatsuba test "Robert L." <No_spamming@noWhere_7073.org> - 2017-05-27 12:08 +0000
      Re: The Karatsuba test lehs <skydda.barnen@gmail.com> - 2017-05-27 07:09 -0700
      Re: The Karatsuba test foxaudioresearch@gmail.com - 2017-05-31 14:23 -0700
        Re: The Karatsuba test Raimond Dragomir <raimond.dragomir@gmail.com> - 2017-05-31 22:04 -0700
    Re: The Karatsuba test "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-06-02 00:48 +0000

#59885 — The Karatsuba test

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?

[toc] | [next] | [standalone]

#59901

Den fredag 26 maj 2017 kl. 23:36:11 UTC+2 skrev 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?

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).

[toc] | [prev] | [next] | [standalone]

#59904

lehs <skydda.barnen@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.

[toc] | [prev] | [next] | [standalone]

#59906

Den lördag 27 maj 2017 kl. 08:33:28 UTC+2 skrev Andrew Haley:
> lehs <skydda.barnen@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.

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.

[toc] | [prev] | [next] | [standalone]

#59908

lehs <skydda.barnen@gmail.com> wrote:
> Den l?rdag 27 maj 2017 kl. 08:33:28 UTC+2 skrev Andrew Haley:
>> lehs <skydda.barnen@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.

[toc] | [prev] | [next] | [standalone]

#59909

Den lördag 27 maj 2017 kl. 08:51:55 UTC+2 skrev Andrew Haley:
> lehs <skydda.barnen@gmail.com> wrote:
> > Den l?rdag 27 maj 2017 kl. 08:33:28 UTC+2 skrev Andrew Haley:
> >> lehs <skydda.barnen@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.

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.

[toc] | [prev] | [next] | [standalone]

#59913

Den lördag 27 maj 2017 kl. 09:07:12 UTC+2 skrev lehs:
> Den lördag 27 maj 2017 kl. 08:51:55 UTC+2 skrev Andrew Haley:
> > lehs <skydda.barnen@gmail.com> wrote:
> > > Den l?rdag 27 maj 2017 kl. 08:33:28 UTC+2 skrev Andrew Haley:
> > >> lehs <skydda.barnen@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.
> 
> 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.

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.

[toc] | [prev] | [next] | [standalone]

#59938

lehs <skydda.barnen@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.

[toc] | [prev] | [next] | [standalone]

#59957

Den lördag 27 maj 2017 kl. 20:34:18 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@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 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.

[toc] | [prev] | [next] | [standalone]

#59964

In article <87k252p2s8.fsf@nightsong.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>lehs <skydda.barnen@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 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

[toc] | [prev] | [next] | [standalone]

#60173

Albert van der Horst wrote:

> In article <87k252p2s8.fsf@nightsong.com>,
> Paul Rubin  <no.email@nospam.invalid> wrote:
> >lehs <skydda.barnen@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

[toc] | [prev] | [next] | [standalone]

#60172

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

[toc] | [prev] | [next] | [standalone]

#59915

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

[toc] | [prev] | [next] | [standalone]

#59921

Den lördag 27 maj 2017 kl. 14:08:53 UTC+2 skrev 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

Right, in English.

[toc] | [prev] | [next] | [standalone]

#60117

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.

[toc] | [prev] | [next] | [standalone]

#60124

joi, 1 iunie 2017, 00:23:55 UTC+3, foxaudio...@gmail.com a scris:
> 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.

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

[toc] | [prev] | [next] | [standalone]

#60171

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web