Recent

Author Topic: Karatsuba multiplication in Linux  (Read 3664 times)

jcaser1948

  • Jr. Member
  • **
  • Posts: 68
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
Thanks in advance

Thaddy

  • Hero Member
  • *****
  • Posts: 14210
  • Probably until I exterminate Putin.
Re: Karatsuba multiplication in Linux
« Reply #1 on: March 14, 2018, 01:48:49 pm »
The GlobalXXX functions are windows specific.
Specialize a type, not a var.

rvk

  • Hero Member
  • *****
  • Posts: 6112
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  ;D

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

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
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.


Thaddy

  • Hero Member
  • *****
  • Posts: 14210
  • Probably until I exterminate Putin.
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.
Specialize a type, not a var.

jcaser1948

  • Jr. Member
  • **
  • Posts: 68
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)

Thaddy

  • Hero Member
  • *****
  • Posts: 14210
  • Probably until I exterminate Putin.
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.
Specialize a type, not a var.

jcaser1948

  • Jr. Member
  • **
  • Posts: 68
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.

Thaddy

  • Hero Member
  • *****
  • Posts: 14210
  • Probably until I exterminate Putin.
Re: Karatsuba multiplication in Linux
« Reply #8 on: March 15, 2018, 03:26:39 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.
That is not good. GMEM_FIXED is a flag for the Windows only GlobalAlloc etc API's. Not a function. In your particular case mmap can be used - somewhat - as a replacement for that when you do not persist the memory.
There are other options though. As suggested before, replace those calls simply by GetMem/FreeMem. That is likely a better option if you have to ask how to use mmap and probably does what you want.
« Last Edit: March 15, 2018, 03:31:33 pm by Thaddy »
Specialize a type, not a var.

 

TinyPortal © 2005-2018