Fast Division by 100 ?

[Ale]

Before I describe an "idea" I had yesterday, let me present the problem:

I like calculators, (handhelds), so I decided to build my own calc, sort of the ultimate model, something like a HP-41 of sorts. (www.hpmuseum.org (http://www.hpmuseum.org))

Well, of course the problem is to perform the actual calculations, no ?. Binary floating point is AFAIK never used. BCD is used instead.
After plenty of research, I decided more or less how I'm going to implement all the math functions, but some low level algorithms are still in the works,
Wenn all this started, I decided for a HC11, but later ended up with an AVR. Easier to work with, much faster, and similar advantages as the PICs and derivatives.
When I discovered the propeller (Thanks to Elekt*r), I thought that could be a good candidate for a better, improved, more functional, usw,. calculator.

In the course of "the ultimate BCD package" (TUBP) I come across finally to the description of how to do "high-performance" BCD calculations (Have a look at the HP-42 simulator for the PC), or the un*x utility bc, included in your OS.
This TUBP uses shorts to hold 4 digits together, but not as packed BCD, but as a binary number. And instead of using BASE 10 is using BASE 10000 !. I wanted to port this to the propeller, but so far so good, the propeller does not bring any speed to the problem http://forums.parallax.com/images/smilies/cry.gif This algorithm relays on multiplication and ... division !, for both bcd multiplication and bcd division. As everyone knows, division is something that is normally avoided for known reasons (speed).

I decided meanwhile, to test a simplified (using bytes instead of shorts) version for the AVR. The problem of multiplication is easily solved, because it has an 8 bit mul instruction... but division ?, that is horribly slow !

I needed a fast, and that means FAST, division by 100. The problem is how ? And unrolled 16 bit by 8 bit division needs ~100 instructions
The division by 10 used to unpack a binary into two digits is done by a table (hehe), can a table be also useful ? http://forums.parallax.com/images/smilies/idea.gif

The number I have to divide is ever hardly above 1100, and I am only going to divide it by 100, so...

Being:

A the dividend
R the remainder
C the hundreds (Quotient in a by 100 division)

A = R + C*100

Great, but how I get C ?

A = R1 + E*128

Dividing A by 128 is straight-forward...
A table can give me C from E, when E is used as index....

table: .byte 0,1,2,3,5,6,7,8,10,11...

Now we get R:

R = A - C*100

R still can be bigger than 100, so a simple compare with 100, and subsequent subtraction, and increment of C, provides both Quotient, and Remainder http://forums.parallax.com/images/smilies/smile.gif

This can be implemented in few bytes (plus the Table), and is going to be Fast !. (A division by 256 instead of 128, is I think not better in terms of performance, but shorter). http://forums.parallax.com/images/smilies/yeah.gif

I know I did not present rocket science, but something I think worth shearing.

Gruß

Ale

[Kaio]

Ale,

please have a look at the webpage of Hacker's Delight. There is a chapter "More on Division by Constants" free for download, which would be very applicable for your problem.
http://www.hackersdelight.org/

Thomas

[Graham Stabler]

I had some friends over at the weekend, one of whom is a programmer, he nearly wet himself when I showed him Hacker's Delight, good book if you like that sort of thing ;)

Graham

[KeithE]

If you like Hacker's Delight, then also check out "Algorithms for programmers" at www.jjj.de/fxt/#fxtbook (http://www.jjj.de/fxt/#fxtbook)

[Harley]

KeithE,

Thanks for the reference to 'Algorithms for programmers'. Pretty fat, 0ver 900 pages!!!
That will take some time to pour over. Something to do this winter. http://forums.parallax.com/images/smilies/yeah.gif

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Harley Shanko

[deSilva]

Ale,
you made some quite questionable remarks in your posting, but I think reading through the given links will be extremely helpful. Also using base 10,000 will most like give you the fastest implementation of multiple precission arithmetik. When coming to fgloeting point it will be the simplest solution to just use Float32...

This is the standard divioson algirithm on the Prop


' Divide x[31..0] by y[15..0] (y[16] must be 0)
' on exit, quotient is in x[15..0] and remainder is in x[31..16]
'
divide shl y,#15 'get divisor into y[30..15]
mov t,#16 'ready for 16 quotient bits
:loop cmpsub x,y wc 'if y =< x then subtract it, set C
rcl x,#1 'rotate c into quotient, shift dividend
djnz t,#:loop 'loop until done
divide_ret
ret 'quotient in x[15..0], rem. in x[31..16]




You can see that there are just 2 instructions per unrolled loop per bitposition of the divisor.

[Ale]

I'll have a look at the books http://forums.parallax.com/images/smilies/smile.gif, thanks in advance.

deSilva:

I had that algorithm in mind, for the implementation on the Propeller of the BASE 10000 BCD.

But, do not forget that I wanted to implement on the AVR, with bytes. AVR has no cmpsub or equivalent, nor has it a barrel shifter, and only 8 bit registers.

Maybe my post is a bit messy on the description side, but I think, and I may be wrong, the problem was described.

Please, will help me if you could point out what are the "questionable remarks" http://forums.parallax.com/images/smilies/smile.gif.

On the AVR: The algorithm I came out with takes as maximum 18 cycles:




ldi ZL,lo8(ptr_to_tbl)
ldi ZH,hi8(ptr_to_tbl)
mov r19,r20
lsl r19
mov r19,r21
rol r19
add ZL,r19
adc ZH,__zero__
lpm r19,Z
ldi ZL,100
mul r19,ZL
sub r20,r19
cpi r20,100
brcs _1
subi r20,100
inc r19
_1:

r19 has the qotient
r20 has the remainder





Is it may be possible to shorten it using a table with steps of 256 instead of 128, but you may not gain too much. http://forums.parallax.com/images/smilies/yeah.gif

Edit: I reviewed the algorithms in Hacker's delight, very interesting indeed. The propeller would probably benefit from some of them, especially the divide by 100 http://forums.parallax.com/images/smilies/smile.gif. Again the AVR lacks a barrel shifter, so does not benefit from these more advanced algorithms. I stay with mine, for this time. Nice books.

Post Edited (Ale) : 9/22/2007 3:56:40 PM GMT

[Don D]

Thought I'd let people know symantec antivirus flags the hackersdelight.org site with a 'downloader' threat!

[Ale]

I do not pretend to be rude, please. But that company can say whatever they want, I really, do not care. I avoid their products as the plage http://forums.parallax.com/images/smilies/smile.gif.

May be they did not understand the difference between a "hacker" and a "cracker". Let's the flames begin http://forums.parallax.com/images/smilies/smilewinkgrin.gif

[Fred Hawkins]

Ale said...
I like calculators, (handhelds), so I decided to build my own calc, sort of the ultimate model, something like a HP-41 of sorts. (www.hpmuseum.org (http://www.hpmuseum.org))


How about a·HP-16C instead?

[Ale]

Fred, what you mean by a HP-16C ?. If I think is the "ultimate" or if I would like to build one like it ?

I do not think is the"ultimate" (but I do like its format).
I built 2 prototypes with that shape http://forums.parallax.com/images/smilies/smile.gif, they are slightly different (I have extra PCBs laying around, too)

A merge between the HP-11 and HP-16 is what the last prototype (when finished) should be like, by the way.

[Fred Hawkins]

That depends on how you define ultimate. For around here, the 16C might be a very useful tool. One key that it has that proved it utility over the years is the BSP (backspace) key. I wish more calcs had that.

[Ale]

The backspace exists also in the 11C and in the 15C (if I remember correctly). These calcs are really good, light, low power (very), and powerful. I had a 12C for several years, later I had the luck of getting a 28S and later a 48SX. Finally 11 years ago I got a 48GX, that still looks like new http://forums.parallax.com/images/smilies/smile.gif.
As ultimate I consider the HP-48. But replicating what they did... can take many many years, considering that most functions are actually in an intermediate language. And everything with a 2 (or 4) MHz processor.

I never ever saw a HP-16, just in HP's catalog from 1984. The HEX->BIN->DEC conversion is what I use most in the HP-48... a bit overkill, but I don't have something else. I hope I can finish mine. (You can get some info on geocities.com/hppacito/calcs.html (http://geocities.com/hppacito/calcs.html) if interested. The second prototype is not there though)

[Fred Hawkins]

HP museum has a link to a windows simulation of the 16C. I think it skips emulating the programming. Low power indeed: ours are circa 1983 and are working on our 3rd or 4th set of batteries.

My 12C provokes my defenestration response every time I hit the E+ key thereby overwriting my saved values in registers 1, 2, 4 and 5. Grrrr. It is the calculator that really should have a bsp key, too.

Thanks for the link. And no, I don't the english for those words either. I like your yellow robot test object which suggests visions of a Bucyrus shovel for my proposed sugar cube board.

[Ale]

HPMuseum has several simulators, HP-42, HP-71, HP-67 (I have one of this, as you saw in the welcome page), HP-45 (I have one of this) and probably others I forgot about. Nice site, loads of nostalgic info.
Todays HP-12 Platinum has a 6502 derivative (I heard without the Y register...), and not anymore a Nut derivative. I have to update the site with the new prototype and some soft for it http://forums.parallax.com/images/smilies/smile.gif.

The HP-1x series did not have that much memory... so some functions used the registers, like statistics. I really do not remember I had problems with the E+ Key... well my fingers were much smaller then (when I was 12 or so...some 20 years ago...)

[Fred Hawkins]

You probably went unscathed because you never used the 16C. That 12C E+ (sigma, summation) key is the CHS (change sign) on the comp scientist calc.

I have to confess that for a decade and a half I used its program to balance my checkbook, savings and cash accounts. (enter the number, press r/s A, B, C, or D) C was for Checking of couse. D was for debt, ie credit card).

[Graham Stabler]

This is an interesting site, in particular the papers in the bibliography:

www.jacques-laporte.org/TheSecretOfTheAlgorithms.htm (http://www.jacques-laporte.org/TheSecretOfTheAlgorithms.htm)

[IAN STROME]

Got an old Casio
Still use it,works in HEX
I'm OK up to 256 but 32bit I need the calc.

Regards Ian
:- When I log on to AOL is says " You got problems "

[Ale]

Thanks Graham !, how long I was looking for that ?...

Some years ago I tried to understand how this worked.. but without knowing the algorithm used... was a bit futile...


IAN said...

:- When I log on to AOL is says " You got problems "



??? I'll dump anything that says that I got any problems http://forums.parallax.com/images/smilies/wink.gif

[Mightor]

Ale said...

??? I'll dump anything that says that I got any problems http://forums.parallax.com/images/smilies/wink.gif

Denial is not just a river in Egypt, you know :)

Gr,
Mightor

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
| To know recursion, you must first know recursion.
| I reject your reality and substitute my own!
| - Adam Savage

[Ale]

Hahahaha, it depends on *who* says it.http://forums.parallax.com/images/smilies/smile.gif

[IAN STROME]

If you can keep your head, when all about you are losing theirs,
It is possible you haven't grasped the gravity of the situation.