Board index » delphi » 2^31 radix integer arithmetic using Int64 type?

2^31 radix integer arithmetic using Int64 type?

Hello,

I find I have to program my own huge integer routines rather than rely
on one of the several excellent packages available.

Can I fish for some help from an expert on 2^31 radix arithmetic using
the Int64 type?

Specifically, is there some super fast way of getting at the carry
when multiplying these things?

The straightforward approach is to compute Floor(product/radix) with
the Extended type (which has 19 - 20 sig figs, while 2^31 has 19
digits, so should be possible).

And indeed this works nicely, except that when I time the whole thing
on my computer, (GenuineIntel Family 6 Model 8 800 MHz Stepping 3), I
find it takes about 50 nanoseconds. On the other hand multiplying two
longwords takes about 3 nanoseconds, so I can accomplish the whole
thing just as fast, even on a naive algorithm, and get a bit extra as
well, by long multipling 4 words as doublewords in 4*4*3 = 48 nano
seconds.

Are these timings plausible?

And if so what can be the advantage of using 2^31 radix arithmetic, as
I believe the packages do? It can only be that there is some faster
way of getting at the carry in 2^31 radix arithmetic I don't know
about.

Help appreciated.

sincerely,
William Boyd

 

Re:2^31 radix integer arithmetic using Int64 type?


On Thu, 13 Feb 2003 00:58:35 GMT, rinpo...@spamcop.net (William Reid

Quote
Boyd) wrote:
>Can I fish for some help from an expert on 2^31 radix arithmetic using
>the Int64 type?

Whoops ! I meant 2^63 of course - too much huge Rembrandt appreciation
going on round here at this moment in time is seemingly still standing
explains everything OK ...

But the  rest flows, I think,  and I should appreciate help. My code
timing routine  follows: HighResTimer is a Freeware component, and
very nice too, that I got off www.torry.net.

  //---- Use RDTSC timing if available (Pentium and some clones)

  HighResTimer.UseTSC:= HighResTimer.TSC;

  //---- GetOverhead

  with HighResTimer do
  begin
    StartTimeMeasure;
    for i:= 0 to NumberIterations - 1 do
         {nothing}
    StopTimeMeasure;
    Overhead:= GetTimeDifference;
    {ShowMessage(IntToStr(Round(Overhead)))}
  end;

//---- Do the timing

  with HighResTimer do
  begin
    StartTimeMeasure;
    Int1:= High(Int64);
    Int2:= High(Int64);
    Extended1:= Int1;
    Extended2:= Int2;
    Int1:=Int1*Int2;
    for i:= 0 to NumberIterations - 1  do
    begin
      CarryF:= Extended1*Extended2/RadixF;
      Carry:= Trunc(CarryF)
    end;
    StopTimeMeasure;
    {ShowMessage(IntToStr(Round(GetTimeDifference)));}
    TaskTime:= Round((GetTimeDifference -
Overhead)*1000/NumberIterations)
  end;
  ShowMessage(IntToStr(TaskTime)); //---- nanoseconds

Other Threads