Ale

09-21-2007, 02:50 PM

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

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