### Author Topic: Karatsuba multiplication in Linux  (Read 1749 times)

#### jcaser1948

• Jr. Member
• Posts: 51
##### Karatsuba multiplication in Linux
« on: March 14, 2018, 01:33:06 pm »
Hi,friends
I thy to use the following Karatsuba multiplication in Opensuse Linux
Code: Pascal  [Select]
1.  procedure Karatsuba(PA, PB, PR: PInt64Array; d: integer);
2.   var
3.     AL, AR, BL, BR, ASum, BSum, X1, X2, X3: PInt64Array;
4.     i, halfd: integer;
5.   begin
6.     if d <= 100 then
7.    begin
8.       GradeSchoolMult(Pa, Pb, Pr, d);// normal multiplikation, definiert woanders
9.       exit;
10.     end;
11.     halfd := d shr 1;
12.     AR := @PA[0];
13.     AL := @PA[halfd];
14.     BR := @PB[0];
15.     BL := @PB[halfd];
16.     ASum := @PR[d * 5];
17.     BSum := @PR[d * 5 + halfd];
18.     X1 := @PR[0];
19.     X2 := @PR[d];
20.     X3 := @PR[d * 2];
21.     for i := 0 to halfd - 1 do
22.     begin
23.       asum[i] := al[i] + ar[i];
24.       bsum[i] := bl[i] + br[i];
25.     end;
26.     Karatsuba(AR, Br, X1, halfd);
27.     Karatsuba(AL, BL, X2, halfd);
28.     Karatsuba(ASum, BSum, X3, halfd);
29.     for i := 0 to d - 1 do
30.       X3[i] := X3[i] - X1[i] - X2[i];
31.     for i := 0 to d - 1 do
32.       PR[i + halfd] := PR[i + halfd] + X3[i];
33.   end;
34.
35. begin
36.   Alen := length(self.fDigits);
37.   BLen := Length(I2.fDigits);
38.   iMin := ALen;
39.   iMax := BLen;
40.   if ALen > BLen then
41.   begin
42.     iMin := BLen;
43.     iMax := ALen;
44.   end;
45.   if (iMin < 80) or (imin < Imax shr 4) then
46.   begin
47.     self.Mult(i2);
48.     exit;
49.   end;
50.   d := 1;
51.   while d < iMax do
52.     d := d * 2;
53.   setlength(self.fDigits, d);
54.   setlength(i2.fDigits,d);
55.   PA := @self.fdigits[0];
56.   PB := @i2.fdigits[0];
57.   HR := GlobalAlloc(GMEM_FIXED, d * 6 * Sizeof(int64));
58.   PR := GlobalLock(HR);
59.   FillChar(Pr[0], sizeof(int64) * 6 * d, 0);
60.   Karatsuba(PA, PB, PR, d);
61.   DoCarry(Pr, self.Base, d * 2);
62.   d := 2 * d;
63.   while (d > 0) and (pr[d - 1] = 0) do
64.     Dec(d);
65.   setlength(self.fDigits, d);
66.   setlength(i2.fDigits, BLen);   {Changes input variable ?????????? GDD}
67.   move(pr[0], self.fdigits[0], d * sizeof(int64));
68.   self.Trim;
69.   self.Sign := self.Sign * i2.Sign;
70.   GlobalUnlock(HR);
71.   GlobalFree(HR);
72. end;

The compiler does not like the sentences
Code: Pascal  [Select]
1. HR := GlobalAlloc(GMEM_FIXED, d * 6 * Sizeof(int64));
2.   PR := GlobalLock(HR
);
and also
Code: Pascal  [Select]
1. GlobalUnlock(HR);
2.   GlobalFree(HR);
Has anyone a suggestion how could convert this procedure easily so that it works under Linux

• Hero Member
• Posts: 7183
##### Re: Karatsuba multiplication in Linux
« Reply #1 on: March 14, 2018, 01:48:49 pm »
The GlobalXXX functions are windows specific.
inline variables like in D10.3 are a bit like Brexit: if you are given the wrong information it sounds like a good idea. Every kid loves candy, but it makes you fat and your teeth will disappear.

#### rvk

• Hero Member
• Posts: 3506
##### Re: Karatsuba multiplication in Linux
« Reply #2 on: March 14, 2018, 01:52:51 pm »
The GlobalXXX functions are windows specific.
Not really a suggestion as to how to convert this to Linux, is it

Has anyone a suggestion how could convert this procedure easily so that it works under Linux

You could try including cmem in the uses and change the GlobalAlloc to malloc and GlobalFree to free.
No need to separately lock and unlock it.

#### marcov

• Global Moderator
• Hero Member
• Posts: 6619
##### Re: Karatsuba multiplication in Linux
« Reply #3 on: March 14, 2018, 02:04:53 pm »
The question is hard to answer without knowing why globalalloc is used.

Under windows 3.1 it was used for nearly every allocation, in that case, replace it with normal getmem/freemem calls.

• Hero Member
• Posts: 7183
##### Re: Karatsuba multiplication in Linux
« Reply #4 on: March 14, 2018, 02:31:48 pm »
The question is hard to answer without knowing why globalalloc is used.

Under windows 3.1 it was used for nearly every allocation, in that case, replace it with normal getmem/freemem calls.
Probably: indeed. But we can not know because it is not used in the fragmentary example.
inline variables like in D10.3 are a bit like Brexit: if you are given the wrong information it sounds like a good idea. Every kid loves candy, but it makes you fat and your teeth will disappear.

#### jcaser1948

• Jr. Member
• Posts: 51
##### Re: Karatsuba multiplication in Linux
« Reply #5 on: March 15, 2018, 12:41:02 pm »
The question is hard to answer without knowing why globalalloc is used.

Under windows 3.1 it was used for nearly every allocation, in that case, replace it with normal getmem/freemem calls.
Thanks and what can I use instead of GMEM_FIXED ? As far as I know this function does not exists in Lazarus (Linux Version)

• Hero Member
• Posts: 7183
##### Re: Karatsuba multiplication in Linux
« Reply #6 on: March 15, 2018, 12:46:42 pm »
You can use the UNIX mmap functionality. Even abstract it away in the interface section to obtain fully cross platform.
Note FPC fully supports this.
inline variables like in D10.3 are a bit like Brexit: if you are given the wrong information it sounds like a good idea. Every kid loves candy, but it makes you fat and your teeth will disappear.

#### jcaser1948

• Jr. Member
• Posts: 51
##### Re: Karatsuba multiplication in Linux
« Reply #7 on: March 15, 2018, 01:04:43 pm »
Thaddy, could you please elaborate on your suggestion? I have added Unix in thr uses clause and replaced GMEM_FIXED   with mmap and it does not compile.