integer division

[piotr5]

not related to multicore, but how do you divide one number through another on a risc-processor? how many ticks does it take?

looking at the documentation, I noticed there is no way to divide one register by another, neither is there divide-by-zero exception. so how will division algorithm look like? what's the fastest implementation, counted from prepared registers to an output of a result and remainder? obviously there are 3 approaches: implement it the way you learned at school, using integers only. or make use of the shifting-operator to get a "divide by two". or make use of floating-point numbers by multiplying a whole number with a fraction. guess the best would be to combine all 3 depending on what the core currently is occupied with.

I'm choosing this example because maybe someone will have an idea how to make use of some other core for this simple task. or maybe someone knows of another method. with x86 assembler I always were wondering why division is done in constant time, and if it would be possible to speed up the machine-code by different approach...

[breathe]

yeah, I heard there is yet no support for the "/".
ps: off topic: a 64bit (64-core)version of the board would be nice.

[fmotta]

[piotr5]

[9600]

Just in case anyone missed it, the Architecture Reference manual was updated just over a week ago to include a table with the op-codes:

http://www.adapteva.com/support/docs/e3 ... ce-manual/ (pp. 130)

[piotr5]

[piotr5]

just to soothe the curious: download the sdk and in gcc/libgcc/config/epiphany/ you will find some implementations. the standard ones take about 50 operations plus 4 ticks for each bit of the result. ieee-754 subdirectory has an even faster algorithm that uses about 20 operations, constant time, but works on floats (i.e. only 24 bit). strange that noone thought of performing this fast algorithm twice (each time getting 16 bits of the result) -- this would still be under 50 operations, faster if the result is 16bit...

[amylaar]

The use of this fast algorithm is dependent on flag_recipsf2, and with good reason: there is no logic provided to get exact
rounding. Thus, the result will tend to be slightly inexact. That's a trade-off between accuracy and speed that's
acceptable / beneficial for a lot of applications, but for exact IEEE rounding, not only would you have to use additional
guard bits, you'd actually have to make sure that you always get the right rounding as if you'd calculated with infinite
precision. It's still possible to use Newton-Raphson for the heavy lifting and doing the rounding adjustments with
some extra calculations and come out well ahead of the cost of the fp-bit.c fall-back code, but providing such a library
function has so far not come up as a requirement important enough to justify the development effort.
AFAICT, for the main parallella potential applications, a bit of inexactness at division is tolerable.

The same is not true for integer division. If you use division in a hash algorithm (if you can get away with only
a slight cost increase due to extra collisions, you should try other hash reductions like mask or multiply), and the
quotient or remainder you use to calculate the hash value is slightly off, your algorithms will fail catastrophically.

Again, you get this exactly right by adding some extra steps, but you'll loose a lot of the speed advantage, and
it's messy to verify that you got the math right everywhere - it's a combination of lookup tables, ad-hoc asssembly
math with short cuts, and calculus. When you're lucky, you can find a lookup table that you can prove to never
cause overflow using calculus. Sometimes you have to cover certain areas with an exhaustive search as only
discrete math effects save you from overflow. That's already messy when you have 64 bit operations to do
32 bit math
(I did that for a divide library version (for -Os) for SH64 - shaped by SH64 pipeline and instruction set idiosyncrasies),
but doing it for a pure 32 bit micro will make it even more complex.

[hamster]

It might surprise you to learn (as it did me) that integer division is often faster in software than in hardware.

On my laptop dividing all the 16 bit integers by each other using "idiv" takes 1m38. If I use a Radix4 routine it takes 1m00.

Because of this, the silicon that could be used for division is better used for other things.

See http://hamsterworks.co.nz/mediawiki/ind ... y_division for source (and ranting)

[piotr5]

problem with long-division in base n, other than base 2, is that in addition to the number of bits for storing the input you need all the bits to fit in the numbers 0...n-1. afterall you multiply the divident with such a number, so for radix4 you need i+2 bits. with 16bit division using a 32-bit int is sufficient, but what do you use for 32-division on a 32-bit computer? your algorithm must change!

I think on a processor with 31-bit integer-multiplication it would be best to use base 256 though. you easily get 16-bit division by a constant, so you can create a 256-entry look-up table for such constants. that's 512 bytes, and as I said they can be spread across the memory of 5 cores, 102bytes each. the only question is how long does it take to read 16 bit from memory that is 2 steps apart, then add 3 steps of the division-algorithm to get total speed...