an old division algorithm lazarus / 62-General ---------------------------------------------------------------------- srvaldez · 2024-10-21 16:43 my adaptation to freePascal of the division algorithm discussed in this paper https://dmsmith.lmu.build/MComp1996.pdf I added some more elements to the array than what was presented in the paper you can experiment increasing the base and thereby increasing the number of digits per element, as the code stands, base 10000000 is max, that's 7 digits per element max, but I recommend that you test it thoroughly before trusting it Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program divide; {$mode objfpc} uses sysutils, math, strings; Const         dimension = 16;        basen =10000;        ln = 4; // number of digits per element, remember to change it if you change basen        function min (const a : longint; const b : longint) : longint;begin  if a < b then min := a else min := b;end; function RealW (var w : array of double; const j : longint) : double;var    wx : double;begin    wx := ((w[j - 1] * basen + w[j]) * basen + w[j + 1]) * basen;    if length(w) >= (j + 2) then wx := wx + w[j + 2];    RealW := wx;end; procedure subtract (var w : array of double; const q : longint; const d : array of double; const ka : longint; const kb : longint);var    j : longint;begin    for j := ka to kb do        w[j] := w[j] - q * d[j - ka + 2];end; procedure normalize (var w : array of double; const ka : longint; const q : longint);begin    w[ka] := w[ka] + w[ka - 1] * basen;    w[ka - 1] := q;end; procedure finalnorm (var w : array of double; const kb : longint);var    carry, j : longint;begin    for j := kb downto 3 do    begin        if w[j] < 0 then            carry := round((-w[j] - 1) / basen) + 1        else      begin            if w[j] >= basen then                carry := -round(w[j] / basen)            else                carry := 0;      end;        w[j] := w[j] + carry * basen;        w[j - 1] := w[j - 1] - carry;    end;end; procedure divide(var result : array of double; const n : array of double; const d : array of double);var    j, last, laststep, q, t, stp : longint;    xd, xn, rund : double;    w : array of double;begin    setlength(w, length(n) + 4+1);    for j := length(n) to length(w) do        w[j] := 0;     t := length(n) - 1;  w[1] := n[1] - d[1] + 1;    w[2] := 0;    for j := 2 to length(n) do      w[j + 1] := n[j];     xd := (d[2] * basen + d[3]) * basen + d[4] + d[5] / basen;    laststep := t + 2;    for stp := 1 to laststep do  begin        xn := RealW(w, stp + 2);        q := floor(xn / xd);      last := min(stp + t + 1, length(W));        subtract(w, q, d, (stp + 2), last);        normalize(w, stp + 2, q);    end;    finalnorm(w, laststep + 1);    if w[2] <> 0 then laststep -= 1;    rund := w[laststep + 1] / basen;    if rund >= 0.5 then w[laststep] := w[laststep] + 1;    if w[2] = 0 then    begin        for j := 1 to (t + 1) do            result[j] := w[j + 1];    end    else    begin      for j := 1 to (t + 1) do            result[j] := w[j];    end;      if w[2] = 0 then result[1] := w[1] - 1 else result[1] := w[1];end;  var        n : array[0 .. dimension] of double;        d : array[0 .. dimension] of double;        result : array[0 .. dimension] of double;        s, digit : ansistring;        i : longint;    begin        n[ 1] := 1;        n[ 2] := 3;        n[ 3] := 1415;        n[ 4] := 9265;        n[ 5] := 3589;        n[ 6] := 7932;         n[ 7] := 3846;        n[ 8] := 2643;        n[ 9] := 3832;        n[10] := 7950;        n[11] := 2884;        n[12] := 1971;        n[13] := 6939;        n[14] := 9375;        n[15] := 1058;        n[16] := 2097;                        d[ 1] := 1;        d[ 2] := 2;        d[ 3] := 7182;        d[ 4] := 8182;        d[ 5] := 8459;        d[ 6] := 0452;         d[ 7] := 3536;        d[ 8] := 0287;        d[ 9] := 4713;        d[10] := 5266;        d[11] := 2497;        d[12] := 7572;        d[13] := 4709;        d[14] := 3699;        d[15] := 9595;        d[16] := 7496;                divide(result, n, d);       Str(round(result[2]), s);        s := Trim(s);        for i:=3 to dimension do        begin                Str(round(result[i]), digit);                digit := Trim(digit);                while (length(digit) < ln) do                        digit := '0' + digit;                 s := s + digit;        end;                                         write(s);        writeln(' exponent = ', trunc(result[1] - 1));        writeln('in my adaptation the decimal point is after the first digit, so 3.14 has an exponent of 0'); end. ---------------------------------------------------------------------- MathMan · 2024-10-21 17:33 Nicely done srvaldez. The paper of D. M. Smith does indeed improve on some of the long division algorithms available at that time. Seen from todays perspective it does have deficits compared to modern implementations. The most fundamental difference is that the estimation of the next quotient element has turned from division to multiplication by inverse - a technique that is now part of every compiler 'magic' when you do a division by a constant. This approach is mainly reflected in the following papers (if you want to study) [ 1 ]: T. Granlund, P. L. Montgomery; Division by invariant integers using multiplication; Proceedings of the SIGPLAN PLDI’94 Conf. [ 2 ]: N. Möller, T. Granlund; Improved division by invariant integers; https://gmplib.org/~tege/division-paper.pdf Using the above allows to utilise the full integer register width for individual 'digits' while also eliminating the majority of 'corrections' that D. M. Smith addresses in his paper. Beside that one also gets blessed with a 4-9 fold reduction in elementary operations. Smith gives ratios between division & multiplication - e.g. 1.14 at ~1000 decimal digits, which is a 14% overhead for division. A modern implementation has a ratio of <=1.03 at the same size. Cheers, MathMan PS - forgot to mention that the ratios relate to comparison of base- case or schoolbook implementations of mult and div. Totally different story for efficient variants. ---------------------------------------------------------------------- Thaddy · 2024-10-21 18:14 Side note: why do you name a const ln? That is a function math... ---------------------------------------------------------------------- srvaldez · 2024-10-21 19:11 it's short for length ---------------------------------------------------------------------- Thaddy · 2024-10-22 07:47 It is the name of the function that calculates the natural logarithm: https://www.freepascal.org/docs-html/rtl/system/ln.html Hence my remark.