GP2X Dividing By 1.5


Squidge

Certified Guru
Joined
Nov 16, 2003
Messages
8,495
Location
UK
Website
Visit site
I'm writing a function to divide a number by 1.5. It should take an integer operand (which will always be in the range 0 - 4096) and give an integer result. Eg. Pass in 216, and get back 144.

At the moment, what I've got is this:

Result = ((Num/3)*2)

Which is fine, but I'd really like a faster way of dividing by 3 if possible.

Or perhaps someone has a way without using the divide?

I don't want to use any floating point (so dividing by multiplication is out I think), and ideally don't want to use masses of memory (so no 4096-byte table).
 

Dzz

stmia r0!, {r2-r9}
Joined
Jan 30, 2006
Messages
1,098
Website
Visit site
Squidge posted on Mar 24 2006 at 05:38 PM said:
I'm writing a function to divide a number by 1.5. It should take an integer operand (which will always be in the range 0 - 4096) and give an integer result. Eg. Pass in 216, and get back 144.

At the moment, what I've got is this:

Result = ((Num/3)*2)

Which is fine, but I'd really like a faster way of dividing by 3 if possible.

Or perhaps someone has a way without using the divide?

I don't want to use any floating point (so dividing by multiplication is out I think), and ideally don't want to use masses of memory (so no 4096-byte table).
For example:

Result = ((Num * 43691) >> 16)

Since you know that Num is never more than 4096, there's plenty of precision for this to be perfectly accurate
 
Last edited by a moderator:

chronomitch

Still Fresh
Joined
Dec 25, 2005
Messages
27
How accurate does this need to be? I've got an idea in mind that uses shifting, but it won't be 100% accurate.
 

Dzz

stmia r0!, {r2-r9}
Joined
Jan 30, 2006
Messages
1,098
Website
Visit site
chronomitch posted on Mar 24 2006 at 05:59 PM said:
How accurate does this need to be? I've got an idea in mind that uses shifting, but it won't be 100% accurate.
His original method:
> Result = ((Num/3)*2)
is not a very accurate way of dividing by 1.5

A very fast way that is not quite perfectly accurate but is more accurate than that is:

Result = ((Num * 171) >> 8)

That would compile down to 2 or 3 instructions
 
Last edited by a moderator:

FluffyPanda

I have 6 little blue things. W00t.
Joined
Nov 25, 2005
Messages
568
Age
42
Location
Italy
Website
www.fluffypanda.com
Best to avoid division if at all possible on arm:

From Writing efficient C for ARM

Division and Remainder
The ARM instruction set does not provide integer division. Divisions are typically
implemented by calling a C-library function (__rt_sdiv for signed and __rt_udiv for
unsigned division). Depending on the numerator and denominator, a 32-bit division takes
20-140 cycles. The division function takes a constant time plus a time for each bit to
divide:
Time(numerator / denominator)
= C0 + C1 * log2(numerator / denominator) =
= C0 + C1 * (log2(numerator) - log2(denominator)).
The current version takes about 20 + 4.3N cycles.
As division is an expensive operation, it is desirable to avoid it where possible. Sometimes
expressions can be rewritten so that a division becomes a multiplication. For example,
(x / y) > z can be rewritten as x > (z * y) if it is known that y is positive and y * z
fits in an integer.
It is best to use unsigned division by ensuring that one of the operands is unsigned, as this
is faster than signed division. This applies both to the division subroutines and to divisions
by a power of two (see 3.2 Division and remainder by powers of two).
In the following sections several methods are discussed to improve division efficiency.
 

Radek

Certified Guru
Joined
Oct 13, 2005
Messages
871
Dzz posted on Mar 25 2006 at 01:09 AM said:
chronomitch posted on Mar 24 2006 at 05:59 PM said:
How accurate does this need to be? I've got an idea in mind that uses shifting, but it won't be 100% accurate.
His original method:
> Result = ((Num/3)*2)
is not a very accurate way of dividing by 1.5

A very fast way that is not quite perfectly accurate but is more accurate than that is:

Result = ((Num * 171) >> 8)

That would compile down to 2 or 3 instructions

If results will be stored in a register then two instruction.

The constant could be bigger but (with bigger value for LSL too) but eventually it might not fit into immediate value for left operand. So extra register would be needed for that constant.

Up to 8 cycles for worst case (7 for mul + 1 for shift).

If we really wanted it fastest possible then:

((x<<2) +x) >> 3

It's multiplying by 0.625 instead of 0.66666666666666666666 (and so on)
but it will be only two (or even "1.5" if last shift can be combined with something
else) opcodes. It will execute in 3 cycles (or just 2 if left operand shifts are free, are they?)

Assuming the x is only 12bit at max then ((x<<2) + x) will result in 15 bit value at max. So... with some masking there is possibility to multiply two 12 bits scalars in 32 bit ALU in one go. If it will be worth I don't know because it will depends how source 12bits values are organized in the memory.
 
Last edited by a moderator:

synkro

0xdeadbeef
Joined
Aug 26, 2003
Messages
823
Location
Germany
Website
Visit site
The accuracy is way better when you use:

((x<<3) + (x<<1) + x) >> 4 == ((x*8) + (x*2) + x) / 16 == x / 1.454545455

This should be a good compromise between speed and accuracy as the max error is approx. (x * 0,04545)
 

Radek

Certified Guru
Joined
Oct 13, 2005
Messages
871
synkro posted on Mar 25 2006 at 03:22 PM said:
The accuracy is way better when you use:

((x<<3) + (x<<1) + x) >> 4 == ((x*8) + (x*2) + x) / 16 == x / 1.454545455

This should be a good compromise between speed and accuracy as the max error is approx. (x * 0,04545)

Yes of course but it takes up to 5 cycles on the Arm9 where multiply takes maximum 7 cycles. So at average it could be around the same speed as mulitply plus LSR.
(and with full multiply accuracy could be even better).
 
Last edited by a moderator:

Epicenter

Very Active Member
Joined
Oct 9, 2005
Messages
2,068
Age
37
Location
USA
Website
www.epicgaming.us or http
In a pinch it's not a bad idea to use decimal multiplication (e.g. Num * 0.5 instead of Num / 2) verus division; in writing 2XMark I learned rather quickly Float math is usually only about 1/4th or 1/5th slower than Integer math, while Division is ENORMOUSLY slower-- half the speed or worse. This will at least ensure maximum accuracy, without a terrible cost in execution speed.
 

paeryn

Reclusive maniac
Joined
Nov 28, 2005
Messages
432
Age
49
Location
Sheffield, England
Website
paeryn.myby.co.uk
Multiplication is register-register only, it doesn't allow for multiplying by an immediate value. It needs 2 cycles + 1 cycle per 8 bits of multiplicand.
As long as you're doing this in batches to allow only setting the multiplicand once outside of the loop then, assuming the value has been calculated (add an extra cycle if reading it from memory,)
(value*43691)>>16 should take 5 cycles.
Dropping down to (value*171)>>8 will take 4 cycles, at the cost of slightly less accuracy.
 
Top