Dividing large numbers

[Wouter]

I'm trying to do some simple arithmetic on very large numbers. I already implemented adding, substraction, multiplying, comparison. I only need to do division but I can't seem to get it working. I already tried a few more complex algorithms and now I just use the algorithm provided by Donald Knuth in the art of computer programming volume 2 (see picture below).

I have two different division VI's the __uintDivide.vi is partly based on what is described: here;

http://kanooth.com/blog/2009/08/implementing-multiple-precision-arithmetic-part-2.html, it is also a description Knuths algo

. The otherone is fully based on how Knuths describes it.

For some reason however I can't seem to get it working. It works for some numbers. For example I have two large integers, represented in a u8 array, the number 50 = Uint1[0,5], number 20 = Uint[0,2]. The LSB is at index 0, the MSB in the last index. For 50 and 20 the result is correct. Also when 20 is 21, 22, 23, 24. When 25 it is in a infinity loop when calculating q*. When trying 19 you also get the wrong result.

I hope someone can help me figuring out what I'm doing wrong? In the book LabVIEW power programming it is implemented as well, I would also be gratefull that if you don't know either what is wrong with my algorithm you could give me some insight in that implementation.

LargeNumbers.zip

Edited January 26, 2012 by Wouter

[Ton Plomp]

The first flaw I could find is the following:

Resolving this doesn't fix the issue though.

What's strange is that if both of these tests are false, the while loop is stale, nother really happens and all values are constant resulting in an endless loop.

How is 20 mod 0 defined by Knuth?

Here you calculate q* and r*. But if I enter 20 mod 0 into my windows calculator it states 'operation undefind'. So the result depends on your compiler, LabVIEW returns 20 for the remainder and 0 for quotient. (sounds valid).

Ton

[Wouter]

Ton that thing you say is wrong is actually correct. q*.v[n-2] is wired to the y input and r*.b+u[j+n-2] is wired to the x input. And the less then comparison has this operation x < y. So... r*.b+u[j+n-2] < q*.v[n-2] => q*.v[n-2] > r*.b+u[j+n-2]

Further the mod function (x mod y) is defined as: if y = 0 then x else x - y * floor(x/y). Thus the same as LabVIEW interpret it. Thus 20 mod 0 = 20.

[Ton Plomp]

There's one catch, if both values are the same then greater than and smaller than aren't congruent.

However I don't really understand the algorithn, though I think that the while loop should never run more than 2 times.

Ton

[Wouter]

However I don't really understand the algorithn, though I think that the while loop should never run more than 2 times.

That is correct. The loop runs always 1 or 2 times.

Further the algorithm is just a schoolbook algorithm when you divide... for example

25 / 32450 \ 1298 (q)

_____25

______74 (r)

______50

______245 (r)

______225

_______200 (r)

_______200

_________0[/CODE]

q* is one of the digits of the quotient and r* is the remainder

Edited January 27, 2012 by Wouter

[Wouter]

Here the full description of the algorithm...

Edited January 28, 2012 by Wouter

[Wouter]

oh and I found one error... The while loop in which q* and r* are calculated is set to "stop if true" this should be "continue if true" because "and repeat this test if r* < b"

(However this fix does not make the code work yet unfortunatly...