Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!bloom-beacon!think!ames!fxgrp!ljz
From: ljz@fxgrp.UUCP (Lloyd Zusman)
Newsgroups: comp.lang.c
Subject: We need  H E L P (!!!!) with an algorithm.
Message-ID: <116@fxgrp.UUCP>
Date: Mon, 12-Oct-87 18:59:27 EDT
Article-I.D.: fxgrp.116
Posted: Mon Oct 12 18:59:27 1987
Date-Received: Wed, 14-Oct-87 01:58:26 EDT
Reply-To: ljz@fxgrp.UUCP (Lloyd Zusman)
Organization: FX Development Group, Inc., Mountain View, CA
Lines: 60
Keywords: extended precision integers
Summary: 64-bit arithmetic

Has anyone out there come across any algorithms for doing arithmetic on 64-bit
integers?  In other words, we want to define a new data type something like
this ...

        typedef struct {
                unsigned long low_order;
                unsigned long high_order;
        } ExtPrecision;

Then, we want to be able to do addition, subtraction, multiplication, and
division on these ExtPrecision things.  Furthermore, we need to be able to
convert between these things and ASCII strings so they can be input and
output from a terminal.

These routines need to be in C (i.e., NOT in assembler), need to be totally
machine independent (with the possible exception of byte-ordering
considerations which can be handled via conditional compilation), and need
to be as fast as possible.  They MUST use integer arithmetic, NOT floating
point.  The routines must look something like ...

        ExtAdd(result, a1, a2)
        ExtPrecision *result;
        ExtPrecision *a1;
        ExtPrecision *a2;
        {}


        ExtSubtract(result, s1, s2)
        ExtPrecision *result;
        ExtPrecision *s1;
        ExtPrecision *s2;
        {}

        ExtMultiply(result, m1, m2)
        ExtPrecision *result;
        ExtPrecision *m1;
        ExtPrecision *m2;
        {}

        ExtDivide(result, remainder, d1, d2)
        ExtPrecision *result;
        ExtPrecision *remainder;
        ExtPrecision *d1;
        ExtPrecision *d2;
        {}

I have already written the routines for adding, subtracting, and multiplying,
and they are very fast.  I'm using the "long division" algorithm in Knuth
which is accurate but slow as hell.  I need something that's exact (insofar
as it produces an exact quotient and remainder) and fast for division, and
alternatively, I could use an entire 64-bit math library.

Any suggestions as to where I might find such a thing, or where I can find
a fast extended-integer division algorithm, or where I can find someone
who could help me with this project?

Thank you in advance for your quick replies.

Lloyd Zusman
...!ames!fxgrp!ljz