Can we beat the 5.81 hours on the TI95 with the HP71B? Gene, Yes we can!



#14

This question was originally ask by Gene in the following post: http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv014.cgi?read=53988:

Quote:
Gene: This is a write-up I just received from Palmer Hanson, who edited the TI PPC Notes for many years in the 1980s - early 1990s. Thought it might be interesting. Looks like the race to 1000 digits on a machine prior to 1990 now belongs to TI? Can we beat the 5.81 hours on the TI95 with the HP71B? :-)

I was not a member of this fine forum at the time of this post. But its never too late (just under 5 years late).

I wrote a spigot program in FORTH and ran it on my 71B this morning. I selected the spigot algorithm for the following reasons:

  1. Spigot programs are very small. Mine is 2x larger because I unrolled the first outer loop. This avoids a conditional statement in the inner loop. Consider the initial loop a method to initialize the array A.
  2. This spigot algorithm requires integers only. A benefit for FORTH.
  3. Spigot programs allow you to watch the action. No need to wait for the final result.

Output:

3141592653589793238462643383279502884197169399375105820974944592307816406286
2089986280348253421170679821480865132823066470938446095505822317253594081284
8111745028410270193852110555964462294895493038196442881097566593344612847564
8233786783165271201909145648566923460348610454326648213393607260249141273724
5870066063155881748815209209628292540917153643678925903600113305305488204665
2138414695194151160943305727036575959195309218611738193261179310511854807446
2379962749567351885752724891227938183011949129833673362440656643086021394946
3952247371907021798609437027705392171762931767523846748184676694051320005681
2714526356082778577134275778960917363717872146844090122495343014654958537105
0792279689258923542019956112129021960864034418159813629774771309960518707211
3499999983729780499510597317328160963185950244594553469083026425223082533446
8503526193118817101000313783875288658753320838142061717766914730359825349042
8755468731159562863882353787593751957781857780532171226806613001927876611195
909216420198
TIME: 11362.03 SEC
1000 digits in 3.16 hours. Almost 2x faster than the TI95. Over 2x faster than BASIC versions in the aforementioned thread.

Code (my first attempt, more optimization can be done):

: SPIGOT ;
: 04D. <# # # # # #> TYPE ;
: DUM* DUP ROT ROT UM* SWAP 2SWAP UM* D+ ;
1000 CONSTANT N
N 4 / 14 * CONSTANT M
5 CONSTANT S
CREATE A M S * NALLOT
VARIABLE B
VARIABLE C
VARIABLE E
10000 CONSTANT F
VARIABLE K
76 4 / CONSTANT MAXL
M DUP B ! C ! 1 K !
: SPIGOTM
0,
BEGIN B @ 1 - DUP B ! 0 > WHILE
B @ DUM*
20000000,
D+
B @ 2* 1 -
M/MOD
ROT
A B @ S * + !
REPEAT
F M/MOD 04D.
DUP E ! 0
  BEGIN C @ 14 - DUP DUP C ! B ! 0 > WHILE
BEGIN B @ 1 - DUP B ! 0 > WHILE
B @ DUM*
A B @ S * + @ F UM*
D+
B @ 2* 1 -
M/MOD
ROT
A B @ S * + !
REPEAT
F M/MOD E @ 0 D+ 04D.
DUP E ! 0
    1 K +! K @ MAXL = IF CR 0 K ! THEN
REPEAT
;
: DOIT
CLOCK
SPIGOTM 2DROP CR CR
." TIME: " CLOCK X<>Y F- STD F. ." SEC" CR
;

Original C program:

#include <stdio.h>
#define NDIGITS 1000
#define LEN (NDIGITS/4+1)*14
int main()
{
int a[LEN];
int b;
int c = LEN;
int d = 0;
int e = 0;
int f = 10000;
int g;
int h = 0;
while ((b = c -= 14) > 0) {
while (--b > 0) {
d *= b;
if (h == 0)
d += 2000 * f;
else
d += a[b] * f;
g = b + b - 1;
a[b] = d % g;
d /= g;
}
printf("%04d", e + d / f);
d = e = d % f;
h = 4;
}
return (0);
}

More spigot info:
http://sense.net/~egan/hpgcc/#Spigot%20Algorithm.


Edited: 28 Feb 2009, 5:35 p.m.


#15

Great job, Egan!!

Cheers,

Peter

#16

I compiled C source with HPGCC for HP-50g and run on it - ~10.5sec @12MHz without sys_slowOff() and ~1.5sec @75Mhz with sys_slowOff()

How to overcklock HP-50g with HP49G+ Clockspeed Adjustment Tools ? May be somebody have sources of this utilities and post it here to adapt them for 50g?


Edited: 1 Mar 2009, 12:27 a.m.


#17

Quote:
I compiled C source with HPGCC for HP-50g and run on it - ~10.5sec @12MHz without sys_slowOff() and ~1.5sec @75Mhz with sys_slowOff()

At 1.5 seconds it probably took longer to start the program than to run it. :-) Sadly the 50g was not available before 1990. Gene was looking for pre-1990 calculators.
Quote:
How to overcklock HP-50g with HP49G+ Clockspeed Adjustment Tools ? May be somebody have sources of this utilities and post it here to adapt them for 50g?

The 49G+ and 50G differ only by the number of ports and batteries, and cosmetically. The 49G+ Clockspeed Adjustment Tools should work as-is with the 50G.

BTW, with HPGCC3 you can overclock to 192MHz.


#18

Quote:
The 49G+ and 50G differ only by the number of ports and batteries, and cosmetically. The 49G+ Clockspeed Adjustment Tools should work as-is with the 50G.

On my HP-50G dont work.
Page at http://www.alpage.ath.cx/ don't open anymore - just blank page.

Please help to find the information that was previously on this page and sources of HP49G+ Clockspeed Adjustment Tools (if posible)
Quote:
BTW, with HPGCC3 you can overclock to 192MHz.

Where download HPGCC3?

Edited: 1 Mar 2009, 7:24 p.m.


#19

Quote:
Please help to find the information that was previously on this page and sources of HP49G+ Clockspeed Adjustment Tools (if posible)

I'd post a message to comp.sys.hp48: http://groups.google.com/group/comp.sys.hp48/topics?lnk
Quote:
Where download HPGCC3?

You'll need to contact the developers directly. See
http://sense.net/~egan/hpgcc3/qsosx.html, #4.
#20

Quote:
Sadly the 50g was not available before 1990. Gene was looking for pre-1990 calculators.

Where do we draw the line between computers and calculators? If we go by machines listed on this forum, considering just hand-held devices, I'll bet that a 94d/e/f programmed in assembly will beat anything else from HP. The 94 BASIC is not terribly fast, but it might give Forth on 71b some competition. I'll have to try it.


#21

Quote:
Where do we draw the line between computers and calculators?

IMHO, GPS units, dive computers, battery-operated watches, and calculators are all computers, albeit fixed or limited purpose. A difference in generation may mean the difference between fixed/limited and general purpose.

I would consider the 71 and the 41 general purpose because they have bidirectional programmable I/O and an alphabet. The book Control the World with HP-IL illustrates how to use the 41 and 71 for many non-calculator specific tasks. Many other calculators, while programmable, lack programmable I/O and an alphabet, limiting it to a fixed or limited purpose.

I know little about any TI. I just downloaded and ran a TI95 emulator. It looks a lot like the 71B. I think Gene's request was fair. I'd like to know if TI95 ASM can best the 71B with the same algorithm.


#22

Quote:
The 94 BASIC is not terribly fast, but it might give Forth on 71b some competition. I'll have to try it.
Unfortunately the 71's Forth was a very poor implementation. Many Forth words could be sped up dramatically by just redefining them in Forth, without even using assembly language. For example, instead of using the built-in CHR$, doing this:
1 STRING CHR$$    "   " ( ie, 2 spaces) CHR$$ S!
CHR$$ DROP CONSTANT CHR$ADR
: CHR$ COMPILE CHR$ADR COMPILE C! COMPILE CHR$$ ; IMMEDIATE
takes more memory, but is fourteen times as fast without even resorting to assembly.
Quote:
The book Control the World with HP-IL illustrates how to use the 41 and 71 for many non-calculator specific tasks.
Nice book, but totally lacks the ambition of interfacing the huge array of available IEEE-488 lab instrumentation through the HP82169A HPIL-to-HPIB interface converter box.

#23

Quote:
Unfortunately the 71's Forth was a very poor implementation. Many Forth words could be sped up dramatically by just redefining them in Forth, without even using assembly language.

True, but I'm still happy its there.

BTW, can you speed this up for me:

SWAP OVER UM* SWAP 2SWAP UM* D+
It takes a double and a single and returns a double product. Something missing from 71B Forth.

An alternative I have tried:

SWAP OVER * >R UM* R> +
is actually a bit slower.

Thanks.


#24

Quote:
True, but I'm still happy its there.
So am I-- I was just airing my disappointment that it wasn't nearly as good as it could have been with the same hardware.
Quote:
BTW, can you speed this up for me:
I have the execution times for a lot of words, but definitely not all of them, and I expect that the multiplication here is the limiting factor. I never got into the assembly language. It would be interesting to know if it's using a BASIC routine (as too many words apparently do), possibly even converting to and from floating-point, instead of having a well-written primitive to do 20-bit fixed-point multiplication with 40-bit result.
#25

Update. I took some time this AM to do a bit of optimization.

Output:

3141592653589793238462643383279502884197169399375105820974944592307816406286
2089986280348253421170679821480865132823066470938446095505822317253594081284
8111745028410270193852110555964462294895493038196442881097566593344612847564
8233786783165271201909145648566923460348610454326648213393607260249141273724
5870066063155881748815209209628292540917153643678925903600113305305488204665
2138414695194151160943305727036575959195309218611738193261179310511854807446
2379962749567351885752724891227938183011949129833673362440656643086021394946
3952247371907021798609437027705392171762931767523846748184676694051320005681
2714526356082778577134275778960917363717872146844090122495343014654958537105
0792279689258923542019956112129021960864034418159813629774771309960518707211
3499999983729780499510597317328160963185950244594553469083026425223082533446
8503526193118817101000313783875288658753320838142061717766914730359825349042
8755468731159562863882353787593751957781857780532171226806613001927876611195
909216420198
TIME: 8935.49 SEC
That's just under 2.5 hours and more than 2x faster than the TI95.

Source:

: SPIGOT ;
: 04D. <# # # # # #> TYPE ;
76 4 / CONSTANT MAXL
1000 CONSTANT N
N 4 / 14 * CONSTANT M
5 CONSTANT S
CREATE A M S * NALLOT
10000 CONSTANT F
VARIABLE E
VARIABLE K
VARIABLE P
: SPIGOTM
1 K !
0,
  1 M 1 - DO
I SWAP OVER UM* SWAP 2SWAP UM* D+
20000000, D+
I 2* 1 - M/MOD
ROT A I S * + !
-1 +LOOP
F M/MOD 04D.
DUP E ! 0
  0 M 15 - DO
1 I DO
I SWAP OVER UM* SWAP 2SWAP UM* D+
A I S * + DUP P ! @ F UM* D+
I 2* 1 - M/MOD
ROT P @ !
-1 +LOOP
F M/MOD E @ 0 D+ 04D.
DUP E ! 0
1 K +! K @ MAXL MOD 0= IF CR THEN
-14 +LOOP
  2DROP 
;
: DOIT
CLOCK SPIGOTM CLOCK
CR CR ." TIME: " X<>Y F- STD F. ." SEC" CR
;
#26

Ok, I think this will be my last optimization.

My original version was developed for 16-bit machines, but the 71B is 20 bits. Using 20 bits I can now calculate 6 digits/outer loop (was 4). This also reduces the overall iteration count by 1/3.

Output:

314159265358979323846264338327950288419716939937510582097494459230781640628620
899862803482534211706798214808651328230664709384460955058223172535940812848111
745028410270193852110555964462294895493038196442881097566593344612847564823378
678316527120190914564856692346034861045432664821339360726024914127372458700660
631558817488152092096282925409171536436789259036001133053054882046652138414695
194151160943305727036575959195309218611738193261179310511854807446237996274956
735188575272489122793818301194912983367336244065664308602139494639522473719070
217986094370277053921717629317675238467481846766940513200056812714526356082778
577134275778960917363717872146844090122495343014654958537105079227968925892354
201995611212902196086403441815981362977477130996051870721134999999837297804995
105973173281609631859502445945534690830264252230825334468503526193118817101000
313783875288658753320838142061717766914730359825349042875546873115956286388235
378759375195778185778053217122680661300192787661119590921642019893
TIME: 6720.22 SEC
1002 digits in 1.87 hours. That's over 3x faster than the TI95.

Source:

: SPIGOT ;
: 06D. <# # # # # # # #> TYPE ;
79 6 / CONSTANT MAXL
1002 CONSTANT N
N 6 / 21 * CONSTANT M
5 CONSTANT S
CREATE A M S * NALLOT
1000000 CONSTANT F
VARIABLE E
VARIABLE K
VARIABLE P
: SPIGOTM
1 K !
0,
  1 M 1 - DO
I SWAP OVER UM* SWAP 2SWAP UM* D+
200000000000, D+
I 2* 1 - M/MOD
ROT A I S * + !
-1 +LOOP
F M/MOD 06D.
DUP E ! 0
  0 M 22 - DO
1 I DO
I SWAP OVER UM* SWAP 2SWAP UM* D+
A I S * + DUP P ! @ F UM* D+
I 2* 1 - M/MOD
ROT P @ !
-1 +LOOP
F M/MOD E @ 0 D+ 06D.
DUP E ! 0
1 K +! K @ MAXL MOD 0= IF CR THEN
-21 +LOOP
  2DROP 
;
: DOIT
CLOCK SPIGOTM CLOCK
CR CR ." TIME: " X<>Y F- STD F. ." SEC" CR
;

Possibly Related Threads...
Thread Author Replies Views Last Post
  HP PRIME - How to convert TICKS in hours, minutes, seconds giancarlo 10 458 11-12-2013, 08:01 AM
Last Post: Harold A Climer
  HP71B Spy Radio Crypto Donald Ingram 2 248 10-14-2013, 10:51 AM
Last Post: Eric Smith
  Bug Bounty Programs Beat Internal Researchers Peter Murphy (Livermore) 0 157 07-12-2013, 06:59 PM
Last Post: Peter Murphy (Livermore)
  HP 50g Takes hours to compute a convergent series Matthew Richards 10 503 05-14-2013, 03:30 PM
Last Post: Thomas Klemm
  HP71B to HP 41 Translator ROM Manual Michael Lopez 5 323 04-25-2013, 03:51 AM
Last Post: Mike (Stgt)
  Rather large missed opportunity - a pile of HP71B's Chris Smith 3 264 04-19-2013, 07:30 AM
Last Post: Chris Smith
  Has anyone else had problems with ebay member 'hp71b'? Dan Grelinger 6 345 01-26-2013, 09:33 AM
Last Post: aurelio
  Gene, are you out there? Dieter 8 373 10-19-2012, 12:04 PM
Last Post: Dieter
  Question to Eric Rechlin & Gene Wright about HP30b/30b repurposing at HHC2012 Namir 2 174 08-04-2012, 05:30 PM
Last Post: Namir
  Programming cable for hp-30b -> wp-34s Open letter to Gene Nigel Rowe 37 1,339 08-02-2012, 12:30 AM
Last Post: Guy Dufour

Forum Jump: