Re: Extended-Precision Division

Terje Mathisen wrote:
>> Matt wrote:
>>> Terje Mathisen wrote:
>>>
>>>> Matt wrote:
>>>
>>> [...]
>>>
>>>>> The division isn't really avoidable, but it isn't part of a
>>>>> critical loop either. I am mostly interested because I know how
>>>>> to extend addition, subtraction, and multiplication out to
>>>>> arbitrary precisions. Division is the only one that I do not know
>>>>> about. It is easy to extend the numerator out to arbitrary
>>>>> precision, but the denominator does not easily follow.
>>>>
>>>> Not at all:
>>>>
>>>> The easy way to solve your assumed problem _exactly_ is to
>>>> calculate a 65-bit accurate reciprocal value, and use this to
>>>> multiply the timestamp difference. Do a final shift, and you have
>>>> the same answer as you'd get from a full division.
>>>
>>> [...]
>>>
>>> Now that I think about it, this seems very reasonable. I can use a
>>> crappy shift-and-subtract algorithm, and I only pay that cost once.
>>> The multiplies may well be as fast as a single divide.
>>>
>>> I am still fairly interested in a more mathematical answer. At
>>> Grumble's recommendation, I have posted the same question in
>>> comp.programming, and already a couple of interesting replies have
>>> come up.
>>
>> The 65-bit reciprocal _will_ give mathematically exact answers.
>>
>> For a proof, search for the article Agner Fog wrote after he & I
>> reinvented the algorithm and proved that it works for all possible
>> combinations of divisor and dividend.

I know...I meant that I'd like to see the mathematics of how to perform long
division. Every grade school child taking Algebra can tell you that X/(Y +
Z) != X/Y * (Y + Z). A reciprocal multiply is a good solution, but it also
requires an existing reciprocal or division algorithm. IIRC reciprocal can
be computed iteratively with only multiplies, but...

I suppose for the reciprocal that means that for Q = X / Y I compute R =
2^65 / Y and Q = (X * R) >> 65?

How exactly do you come by 65-bit reciprocal? Rather, what is the
significance of 65 bits?

-Matt

.

Relevant Pages

  • Re: Non-polynomial factorization, critical point
    ... FUNCTIONS tell the math ... in an INFINITY of ways, so how does the mathematics ... multiplies. ...
    (sci.math)
  • Re: Non-polynomial factorization, critical point
    ... where the a's are roots of ... The mathematics will not let you ... So the 7 cannot be divided off in general, so math ... How can the math pick and choose how 7 multiplies ...
    (sci.math)
  • Re: DARPA, at least, has a clue (maybe, sometimes)
    ... Some mathematics are lucky to have order as a property. ... sort of "surprise" that makes me suspicious of your analogies. ... Your last sentence only multiplies as the code base increases. ... hardware guys who had their own hard problems. ...
    (comp.arch)
  • ONLY AGREEMENTS EXIST: JOSHUA
    ... to stay in the ring of algebraic integers. ... with mainstream mathematicians not doing anything that I can notice, ... the mathematical truth then human progress in mathematics ends. ... functions can push back outward to change how that 7 multiplies, ...
    (sci.math)
  • Re: JSH: Understanding the arguments
    ... which is trivially true when you have polynomials. ... to stay in the ring of algebraic integers. ... the mathematical truth then human progress in mathematics ends. ... functions can push back outward to change how that 7 multiplies, ...
    (sci.math)