HP Forum Archive 18

[ Return to Index | Top of Index ]

Ongoing Pi Programming Contest Message #1 Posted by Katie Wasserman on 18 Oct 2008, 12:20 a.m. Like many of you, I'm afflicted with the many-digits-of-pi disease and love trying to get the most out of programming HP calculators. I also often enjoy a programming contest that's presented here, so I propose the following, ongoing contest: On your favorite HP calculator of limited memory, no more than 1K bytes, how many decimal digits of pi can you store in memory using any programming method you wish. The only stipulations I would make are: 1) The result has to be in consecutive memory registers. 2) Decimal point positions are irrelevant and leading zeros can be assumed. 3) The program has to run to completion before the battery dies (i.e., the program has to really execute). To get this contest started I've posted what I've come up with for 4 different calculators here. notes: The 16C is in an interesting challenge since it's memory allocation is so flexible. On the original 12C you can do better than 70 digits using the trivial program: 3 . 1 4 1 5 9 2 6 5 3 STO 0 5 8 9 7 9 3 2 3 8 4 STO 1 ... ... Continuing this to 'STO 7' will give you 79 decimal digits, but that's no fun! -Katie Edited: 18 Oct 2008, 12:21 a.m.

Re: Ongoing Pi Programming Contest Message #2 Posted by Kiyoshi Akima on 21 Oct 2008, 1:32 p.m., in response to message #1 by Katie Wasserman Continuing in the brute-force manner, one can get 260 digits on an HP-67 simply by reading in a data card (albeit with manual intervention to turn the card over). On an HP-41C with one memory module (which is still under 1KB memory) one can get about 600 digits with a program to read a data file from an IL mass storage device. One could pack 20% more digits by using the exponent as well. The first twelve digits would then be 3141592653e59. I've got some further ideas I want to try on my 16C when I get home.

Re: Ongoing Pi Programming Contest Message #3 Posted by PeterP on 21 Oct 2008, 3:33 p.m., in response to message #1 by Katie Wasserman is an interactive program allowed where the user enters some digits and then presses a button upon which the calc stores the numbers and asks for the next numbers until all are stored?

Re: Ongoing Pi Programming Contest Message #4 Posted by Katie Wasserman on 21 Oct 2008, 6:12 p.m., in response to message #3 by PeterP Quote: is an interactive program allowed where the user enters some digits and then presses a button upon which the calc stores the numbers and asks for the next numbers until all are stored? I think that's going too far. The program should be self contained with the exception of maybe clearing memory and/or setting modes. The goal is to be creative, figuring out a LZ-type compression scheme for the digits, finding small fractions that give the needed results, etc.. I think that the machines that have shared memory registers and program space are the most interesting to try this on, but the 67/97 and 29C/19C would be also be pretty challenging.

Re: Ongoing Pi Programming Contest Message #5 Posted by PeterP on 21 Oct 2008, 7:23 p.m., in response to message #4 by Katie Wasserman I think you should state the challenge in a more concrete form. Reading in the data from HP-IL is identical to typing it in manually as it has to be created on the HP-IL device first. On the HP41, I could 'write' a program which has the digits, 12 digits at a time in the Alpha in each program step. They hence would be 'stored' in the computer and could be 'recalled' by running the program which would put them 12 digits at a time into the screen. All very boring. Why not try a set of challenges with maybe some kind of deadline... (Attention - severe plagiarism follows...) How to make Pi 'Cook' Write a program CALC. to calculate as many digits of pi as possible and store it in the memory of the calculator. Optimize for time and number of digits. Larger programs will allow you to calculate more digits in less time, but will consume more memory and leave you with less space to store the digits. 'Cut' Write a program (UN)PACK. For packing, (UN)PACK requires as its input a memory space where the digits of pi are stored and will pack them as tightly as possible. Optimize for speed and % reduction in memory space. For displaying the digits, (UN)PACK requires as its input a packed memory space from which it will read, unpack and display the digits. Optimize for speed. 'Consume' Combine CALC and (UN)PACK to store as many digits of pi in your calcs memory and then display them from memory to the user. Iterative calls to CALC and (UN)PACK are allowed as long as (UN)PACK only displays digits that remain stored in the memory after all programs have run their course. (so - calc some digits - pack them - calc some more digits - pack them - ... - unpack and display them). Optimize for speed and number of digits stored. You may use any HP calculator of your choosing, submissions will be ranked by calculator.

Re: Ongoing Pi Programming Contest Message #6 Posted by Egan Ford on 21 Oct 2008, 9:49 p.m., in response to message #5 by PeterP Quote: You may use any HP calculator of your choosing, submissions will be ranked by calculator. Fine. I select the 50g. Cook. I've computed 200,000 digits of Pi using an ArcTan method. Time: 62789 seconds (just under 17.5 hours). Had I used HPGCC3 it would have been 2.5x faster. Cut. I stored the results on the SD card (its memory too :-) Comsume. Well the 50g has a text viewer for viewing the file. No need to write anything. Code, results, screen shots all here: http://sense.net/~egan/hpgcc/#Machin. Final output screen/stats: Edited: 21 Oct 2008, 9:56 p.m.

Re: Ongoing Pi Programming Contest Message #7 Posted by Gerson W. Barbosa on 22 Oct 2008, 8:20 a.m., in response to message #6 by Egan Ford 200,000 digits! Congratulations! Well, the tiny HP-32SII program below gives out 24 digits. In fact it just retrieves the hard-coded pi in HP calculators: P01 LBL P P02 RAD P03 pi P04 1.E-11 P05 - P06 ENTER P07 SIN P08 1.E-23 P09 * P10 x<>y P11 RTN XEQ P 3.14159265358 x<>y 979,323,846,264 Since we're talking about pi, let me present a new pi approximation: '355/113-1/(533+44^4)' = 3.1415926535897866 By using it I'd be able to compute the lenght of a circle with a radius of 1 astronomic unit and get an error as small as 5/64 inches (2 mm). Regards, Gerson.

Re: Ongoing Pi Programming Contest Message #8 Posted by Egan Ford on 22 Oct 2008, 12:21 p.m., in response to message #7 by Gerson W. Barbosa I do not have a 32SII (I should probably get one). I do get the same on a 35s. I didn't know any calc had 24 digits stored internally. Thanks.

Re: Ongoing Pi Programming Contest Message #9 Posted by Jeff Kearns on 23 Oct 2008, 2:02 p.m., in response to message #8 by Egan Ford P08 should read 1.E23 instead of 1.E-23. You learn somethin' new everyday!

Re: Ongoing Pi Programming Contest Message #10 Posted by Gerson W. Barbosa on 23 Oct 2008, 5:48 p.m., in response to message #9 by Jeff Kearns Quote: P08 should read 1.E23 instead of 1.E-23. You're right! Sorry for the typo. Quote: You learn somethin' new everyday! Take a look at this interesting thread started by Rodger Rosenbaum - read Karl Schneider's message #3 first: http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv016.cgi?read=103151 Actually, all Saturn-based machines have 31-digit pi internally, according to Rodger Rosenbaum in another thread. Gerson. Edited: 23 Oct 2008, 5:52 p.m.

Re: Ongoing Pi Programming Contest Message #11 Posted by Katie Wasserman on 23 Oct 2008, 10:28 p.m., in response to message #10 by Gerson W. Barbosa The calculator firmware running in the HP 100/200LX has 32 digits of pi and displays 16 digits. This program is one of the finest RPN implementations HP ever came up with, they should use the source code for this as the model for their current models -- the financial calculations and solver are exceptionally well done.

Re: Ongoing Pi Programming Contest Message #12 Posted by Gerson W. Barbosa on 24 Oct 2008, 6:19 a.m., in response to message #11 by Katie Wasserman Yes. I don't have mine here but I think it can display the other 16 digits with the same technique. I like the HP-200LX Solver too. And of course all those 16 digits. On what other HP calculator could I check the approximation pi ~ '355/113-1/(e^e^e-65650)'?

Re: Ongoing Pi Programming Contest Message #13 Posted by Egan Ford on 21 Oct 2008, 9:34 p.m., in response to message #4 by Katie Wasserman Quote: figuring out a LZ-type compression scheme for the digits Pi does not compress. Compression relies on some type of reoccurring data. E.g. if I try to compress the first 1,000,000 ASCII digits of Pi with bzip2 I can shrink it down to 431,435 bytes, whereas if I had just stored Pi as base 256 I could have use 415,242 bytes. All the compression did was get rid of the ASCII white bits and it still was not as small as just rewriting as base 256. I cannot compress a base 256 file of Pi digits, e.g. I computed the first 1000 and 10000 base 256 digits of Pi and tried to compress with bzip2 and got the following results: File Input file size Output file size ---------- --------------- ---------------- hex.bin 1001 1296 hex10k.bin 10001 10478 The 41C can store 6 ALPHA bytes that can be assigned values 0-255 with XTOA. So that's 14 Pi base 10 digits packed as 6 base 256 digits. In 146 registers (just under 1K) that would be a max of 2044 base 10 Pi digits. IIRC, a 41C with a single memory module has 127 registers for a max of 1778 digits. With some effort I think your spigot program could be adapted to produce base 256 numbers on the 41C+XM and possibly exceed 1000 base 10 Pi digits. Of course you carefully stated in your challenge, decimal digits of Pi, that alone tosses out base 256 and compressed stored results. Edited: 21 Oct 2008, 10:13 p.m. after one or more responses were posted

Re: Ongoing Pi Programming Contest Message #14 Posted by PeterP on 21 Oct 2008, 10:12 p.m., in response to message #13 by Egan Ford For the 41, one can in fact store 14 hex digits per reg which is the highest information density per byte available. storing Alpha data throws away the first byte by using it to mark the following data as alpha data (value 10). Quote: Of course you carefully stated in your challenge decimal digits of Pi, that alone tosses out base 256 and compressed stored results. Not sure if you refer to Katie or my suggestion, but I think storing in any base is just fine as long as your view program can unpack the stored information and view the digits in base 10. A text viewing program showing pi digits in base 256 does clearly not qualify... The 'challenge' part here is to balance the memory allocation between the program to calc and compress the digits and the storage for the digits. Clearly this is not very interesting for modern calcs with quasi unlimited storage (an SD card!) but interesting for say a 41cx or the hp12C. I was always very impressed with these programs from Katie that were able to elicit 100s of digits of Pi from very humble HP's. This challenge is simply the next step in combining the calculation with storage and balancing the memory between calculation and storage. After you swamped us with digits via the hp50 + SD card, why not write a program for the HP15 or your new playground the HP41? I'm sure you can equally amaze us with the number of digits you can cajole these two calcs to calc, store and deliver... Cheers Peter

Re: Ongoing Pi Programming Contest Message #15 Posted by Egan Ford on 21 Oct 2008, 10:18 p.m., in response to message #14 by PeterP Quote: For the 41, one can in fact store 14 hex digits per reg which is the highest information density per byte available. storing Alpha data throws away the first byte by using it to mark the following data as alpha data (value 10). I was aware of the 7th byte, but is there any way from RPN to get to that 7th byte? Quote: Not sure if you refer to Katie or my suggestion, but I think storing in any base is just fine as long as your view program can unpack the stored information and view the digits in base 10. A text viewing program showing pi digits in base 256 does clearly not qualify... My reply was to Katie's suggestion of a LZH compressor. Edited: 21 Oct 2008, 11:29 p.m. after one or more responses were posted

Re: Ongoing Pi Programming Contest Message #16 Posted by PeterP on 21 Oct 2008, 11:09 p.m., in response to message #15 by Egan Ford Yes there is. Conceptually here is how you can store 14 hex digits in any user reg: Create the NNN ('non-normalized number') in the X-reg in stack via any of the many CODE programs (they all take a 14 digit alpha string and interpret it as hex numbers) move the 'Curtain' (aka the abs adress of reg 00) to a convenient place store the x-reg into that reg restore the curtain to its original position Also, there are a number of non-normalized sto and rcl routines available that accomplish the above directly. Last but not least, there are the peek and poke commands from the CCD modul. If you enjoy playing around with synthetic programming, I highly recommend a configuration with CCD OS-X from Raymond del Todo and the SANDBOX from Angel Martin in your clonix. CCD-OS-X has the OS extensions from the CCD implemented in a 4k module which allows easy access to all Status regs - they can be directly addressed as all other stack regs via STO - . - M for example. Very handy! And the SANDBOX from Angel is probably my favorite module ever. It combines the 'best off' from dozens of modules and individual articles and has pretty much anything you can want for programming, synthetic programming, some extra math, lots of Alpha handling and some fun stuff. It even has a full blown memory editor for those lte night MCODE urgings... Anyway, with these two modules in play, there is very little you will have difficulty with to do on the HP41. A note to CODE/DECODE - they were one of the key-part of synthetic programming and until MCODE came around people invented ever faster CODE programs to generate these NNNs. The Sandbox naturally has superfast MCODE versions... A note to NNN. IICR NNNs were first invented and used for HP67 by the PPC members. In an effort to 'dwarf such attempts' HP put some very picky 'normalization' routines into the HP 41 that would force all numbers to conform to these rules. Well, they should have known better. Noone and nothing 'dwarfs' the combined assault from the likes of Wickes, McGeechie & Co. NNN were still discovered and they uses exploited. The rest is history... One can also use an all-bug HP41C to store a NNN in any register as it allowed via the 'IND bug' to access any register in the HP 41 memory (with the exception of XM but that came much later...) Getting your hands on an all-bug 41C, now that is an entirely different story alltogether... Edited: 21 Oct 2008, 11:10 p.m.

Re: Ongoing Pi Programming Contest Message #17 Posted by V-PN on 22 Oct 2008, 2:01 a.m., in response to message #14 by PeterP IIRC there's an algorithm in base 16 (hex) that can calculate consequent digits easily. but how to show base 16 as decimal?

Re: Ongoing Pi Programming Contest Message #18 Posted by Egan Ford on 22 Oct 2008, 2:51 a.m., in response to message #17 by V-PN E.g., take the base 16 number 0.243F. To convert to base 10 (or A from a hex point of view) do the following: 0.243F * A = 1.6A76, take the fractional part and repeat 0.6A76 * A = 4.289C 0.289C * A = 1.9618 0.9618 * A = 5.CDF0 etc... Do this floor(length of digits after decimal * log1016) times, any more will be inaccurate, e.g. floor(4*log1016) = 4 times. Your base 10 number is on the left side of the decimal, IOW 0.243F16 = .141510. And that is how you convert the first 4 hex digits of Pi to decimal. Edited: 22 Oct 2008, 3:39 a.m.

Re: Ongoing Pi Programming Contest Message #19 Posted by Katie Wasserman on 22 Oct 2008, 1:39 a.m., in response to message #13 by Egan Ford Quote: Pi does not compress. Compression relies on some type of reoccurring data. E.g. if I try to compress the first 1,000,000 ASCII digits of Pi with bzip2 I can shrink it down to 431,435 bytes, whereas if I had just stored Pi as base 256 I could have use 415,242 bytes. All the compression did was get rid of the ASCII white bits and it still was not as small as just rewriting as base 256. I was just throwing out some ideas at random, not really intending that this would be a good (or possible) idea. I certainly understand the ASCII vs binary aspect of compression. However, I don't think that the randomness of pi has been proven -- did you see the movie or read the book, Contact? :) Probably the first million digits may not compress much at all. On the other hand a more limited number of digits, as would fit on a 1K calculator, might compress a bit.

Re: Ongoing Pi Programming Contest Message #20 Posted by Egan Ford on 22 Oct 2008, 3:32 a.m., in response to message #19 by Katie Wasserman Quote: However, I don't think that the randomness of pi has been proven I do not believe that Pi is random at all. Truly random strings of numbers cannot be described by an equation or a precise statement like, its the ratio of the circumference divided by the diameter. IMO, irrational numbers cannot be compressed by context unaware methods of compression like traditional data compression (e.g. LZH). Your programs are a type of context aware compression from a certain point of view; they produce more bytes of data than they contain. Quote: On the other hand a more limited number of digits, as would fit on a 1K calculator, might compress a bit. Most traditional data compression methods benefit from larger data block sizes; its more computationally expensive, but the resulting output is usually smaller. Of course 1K of Pi digits isn't Pi and isn't irrational, so anythings possible, right? However, if 1K did compress the program and extra data would probably exceed any benefit.

Re: Ongoing Pi Programming Contest Message #21 Posted by V-PN on 22 Oct 2008, 3:46 a.m., in response to message #20 by Egan Ford Because of just the first digits to fit into 1K it is possible to fit the (de)compression so that a specialized solution could get more digits out of the 1K Opinions?

Re: Ongoing Pi Programming Contest Message #22 Posted by Marcus von Cube, Germany on 22 Oct 2008, 4:43 a.m., in response to message #20 by Egan Ford Pi isn't random, of course. But to standard compression algorithms, it looks random, because they do not "see" the structure behind the flow of digits. If you define "compression" as a representation of some data which occupies less space than the human readable form of the same data, then any algorithm that generates the digits of Pi can be considered a compressed representation of Pi. Since the number of digits of Pi is infinite, the compression ratio is infinite, too, no matter how large the program to generate it is. :) Here is a much simpler example: 1/3 is a "compressed" form of 0.333... with the same compression ratio. Edited: 22 Oct 2008, 4:44 a.m.

Re: Ongoing Pi Programming Contest Message #23 Posted by Diego Diaz on 22 Oct 2008, 6:37 a.m., in response to message #22 by Marcus von Cube, Germany Hi, Just for fun... But considering the amount of memory limited to 1K (bytes?) I'll assume that one can have a much larger memory in his/her calculator as far as you don't exceed that limit... and... that memory could be also considered as a fairly large (8,192) amount of "bits". Whit this in mind, any M-code programmer (well, may be just a few of them :-)) can pack 3 decimal digits (o-999) into a 10bit (HP-41) word; sort of base 1024, just doing DEC->BIN conversion to "pack"and BIN->DEC to unpack. Converting these 8,192bits into 10bits words: 819,2 words. Assigning 3 digits of PI to each word gives: 2,457digits. You'll have to take three digits off the count for every word your program neeeds for the task... however I still think that this mark is hard to beat... regrettably, I'm not an M-code programmer so I'll never know. :-( Cheers. Diego.

Re: Ongoing Pi Programming Contest Message #24 Posted by PeterP on 22 Oct 2008, 8:46 p.m., in response to message #23 by Diego Diaz I'll leave my circle of knowledge here, so please someone correct my gibberish: Actually, I'm not so sure that this suggestion is within the specs or helpful. First, one would have to write into Q-RAM instead of user-ram as the latter is simply 7 bytes to a register. Which means that the 'available' RAM in a 41 just skyrocketed to whatever you and the other hardware geniuses make available to the geeks. Want an extra 4096 words? sure, no problem, NoV64 has plenty of pages and banks you can address through simple words at the h4100 address... And then there is MOARP... Secondly, I think that the actual use per word is dependent on the hardware implementation of the WROM/CXISA commands that are used to read and write to Q-RAM and hence out of the hands of the programmer. For example, some EPROMS store the lower 8 bit in one EPROM and carefully pack the upper 2 bit three at a time into a 2nd EPROM. Others just 'waste' the remaining 6 bits of memory per byte as memory is so cheap. I actually don't know what implementation method you and Meindert used to store the 2 bits. Thirdly, if your program simply stores the digits in Q-RAM its total memory requirement is at least 4 words of total memory per word of stored digits. You need one command to load the 3 digits - 1st word one to set the right address - 2nd word (very generous assumption...) one to write it to Q-RAM - 3rd word one word in Q-RAM space to store it. - 4th word This does not look very promising to me... As Katie stated,this challenge is most interesting for calcs with shared program and storage memory so that one has to optimize how much RAM to use for program vs storage. Cheers Peter

Re: Ongoing Pi Programming Contest Message #25 Posted by Meindert Kuipers on 23 Oct 2008, 3:27 a.m., in response to message #24 by PeterP I was following this thread 'at a distance' but cannot help commenting. With the MLDL2000 we have a total of 255 + 63 (or 255 + 127) 4K pages available of 16 bits each. Of these 16 bits 6 bits are thrown away, no packing is used. Assuming that at least one page is used to store a ROM with the code this is about 1.2 MByte, so with some smart packing (3 digits per bytes) a few million digits can be stored. To be honest, the current firmware does not allow access to all 16 bits yet, but that is not too difficult to implement. With the new MLDL2000 I can support SDHC cards, so the 2 GByte limit of a single SD card does not exist anymore. My mobile phone already has an 8 GByte micro SD card .... Meindert

Re: Ongoing Pi Programming Contest Message #26 Posted by PeterP on 23 Oct 2008, 10:24 a.m., in response to message #25 by Meindert Kuipers that was my suspicion - with memory becoming so cheap, the throwing away of 6 bits is not relevant anymore (but it was back in the day with the EPROMS). Cheers Peter

Re: Ongoing Pi Programming Contest Message #27 Posted by Kiyoshi Akima on 22 Oct 2008, 2:43 p.m., in response to message #1 by Katie Wasserman Quote: The program should be self contained with the exception of maybe clearing memory and/or setting modes. By taking the memory-clearing and mode-setting out of the program I was able to trim seven bytes off Katie's original 16C program, freeing up a register and getting thirteen additional digits for 208 total. I've tested it for 30+ digits; I won't know about the 208 until tomorrow morning. Set the calculator to HEX, 2's COMPL, 56 WSIZE, and CLEAR REG, then RTN and R/S. After 19 hours (estimated), switch to DEC and read the results in registers 0 through .0, thirteen digits each. 01: 2 ; 708 decimal (value may need tweaking) 02: C 03: 4 04: LBL B 05: STO .1 06: 0 07: STO I 08: LBL C 09: GSB 8 10: x 11: RCL .1 12: RCL (i) 13: x 14: + 15: ENTER 16: ENTER 17: RCL .1 18: SL 19: 1 20: + 21: / 22: STO (i) 23: R down 24: LST x 25: RMD 26: X <> I 27: F 28: X <> Y 29: X > Y 30: GTO D 31: 1 32: + 33: X <> I 34: GTO C 35: LBL D 36: 2 37: STO 0 38: RCL .1 39: 1 40: - 41: X > 0 42: GTO B 43: 1 44: 0 45: STO I 46: 0 47: LBL E 48: GSB 7 49: GSB 8 50: - 51: X < 0 52: GTO F 53: STO (i) 54: 1 55: GTO 9 56: LBL F 57: 0 58: LBL 9 59: DSZ 60: GTO E 61: LBL 7 62: RCL (i) 63: + 64: STO (i) 65: RTN 66: LBL 8 67: 9 ; 10000000000000 decimal 68: 1 69: 8 70: 4 71: E 72: 7 73: 2 74: A 75: 0 76: 0 77: 0

Re: Ongoing Pi Programming Contest Message #28 Posted by Kiyoshi Akima on 23 Oct 2008, 2:32 p.m., in response to message #27 by Kiyoshi Akima This program does indeed produce 208 correct decimal digits. In fact, the constant 708 at the beginning is conservative, 690 (2B2 hex) should be adequate.

Re: Ongoing Pi Programming Contest Message #29 Posted by Katie Wasserman on 23 Oct 2008, 11:20 p.m., in response to message #28 by Kiyoshi Akima While I like your use of the implied RTN at the end of the program to save a byte, Dijkstra (among others) would have been appalled! :)

Re: Ongoing Pi Programming Contest Message #30 Posted by Kiyoshi Akima on 24 Oct 2008, 6:00 p.m., in response to message #29 by Katie Wasserman And do you think they would be any happier with the readable constant following LBL 8? Not to mention the 6 GTOs (even if they are used in a structured fashion). There are other things I'm not completely satisfied with. (Including the trailing preposition at the end of the previous sentence.) For one, I'm not convinced the 56-bit wordsize is optimal. A smaller wordsize would put fewer digits in each register, but may allow more registers. On the other hand, a longer wordsize would put more digits in each register, albeit with fewer registers. In particular, I'm thinking I can get 14 registers of 15 digits each, for a total of 210 digits, two better than the current program. Even better would be 14 and 16 (or 16 and 14) for 224. And even better would be 15 and 15 for 225. I'm also unhappy that I posted a suboptimal program. The readable constant I mentioned above could be programed as [F,4,2,4,0,ENTER,*,A,*] saving two more steps. And the [SL,1,+] to compute 2i+1 could be shorted to [SF 4,RLC] (try that on any other Voyager series machine!) I hope to be tinkering with it over the weekend.

Re: Ongoing Pi Programming Contest Message #31 Posted by Katie Wasserman on 24 Oct 2008, 11:39 p.m., in response to message #30 by Kiyoshi Akima Yes these programs are certainly abysmal from a readability and structure standpoint, but they are fun to write! Quote: [SL,1,+] to compute 2i+1 could be shorted to [SF 4,RLC] Very nice! I played with the word size on the 16c quite a bit and found that 56 bit's was optimal for my approach. It also had the advantage of being able to build the word size setting into the program with minimal overhead. The need to multiply by a number up to log2(10) * number_of_digits means that several digits in each register are going to be wasted in order to avoid overflow. I tried to use the double precision functions on the 16C but this took many program steps and killed the advantage of using them. Maybe you'll be able to figure out how to avoid the overflow and if you do, I'll bet that a 64 bit word size will be optimal. Good luck with your weekend tinkering!

Re: Ongoing Pi Programming Contest Message #32 Posted by Kiyoshi Akima on 26 Oct 2008, 1:42 p.m., in response to message #31 by Katie Wasserman Well, here's my current attempt at 64 bits. Continuing to decrease readability, and cheating just a bit: 001 - 43,22, b LBL B 002 - 44 F STO F 003 - 0 0 004 - 44 32 STO I 005 - 43,22, C LBL C 006 - 21 8 GSB 8 007 - 20 x 008 - 45 F RCL F 009 - 45 31 RCL (i) 010 - 20 x 011 - 40 + 012 - 36 ENTER 013 - 36 ENTER 014 - 45 F RCL F 015 - 43, 4, 4 SF 4 016 - 43 C RLC 017 - 10 / 018 - 44 31 STO (i) 019 - 33 Rv 020 - 43 36 LSTx 021 - 42 9 RMD 022 - 42 22 x<>I 023 - E E 024 - 43 49 x=y 025 - 22 d GTO D 026 - 33 Rv 027 - 1 1 028 - 40 + 029 - 42 22 x<>I 030 - 22 C GTO C 031 - 43,22, d LBL D 032 - 2 2 033 - 44 0 STO 0 034 - 45 F RCL F 035 - 1 1 036 - 30 - 037 - 43 30 x>0 038 - 22 b GTO B 039 - E E 040 - 44 32 STO I 041 - 0 0 042 - 43,22, E LBL E 043 - 21 7 GSB 7 044 - 21 8 GSB 8 045 - 30 - 046 - 43 30 x>0 047 - 44 31 STO (i) 048 - 0 0 049 - 43 C RLC 050 - 1 1 051 - 42 10 XOR 052 - 43 23 DSZ 053 - 22 E GTO E 054 - 43,22, 7 LBL 7 055 - 45 31 RCL (i) 056 - 40 + 057 - 44 31 STO (i) 058 - 43 21 RTN 059 - 43,22, 8 LBL 8 060 - 1 1 061 - 8 8 062 - 6 6 063 - A A 064 - 0 0 065 - 36 ENTER 066 - 36 ENTER 067 - 20 x 068 - 20 x Set to HEX, 2's COMPL, 0 WSIZE, CLR REG, RTN, then enter the loop limit 2B8 (696 decimal) and R/S. 14 registers of 15 decimal digits each for 210 digits. Even with the bit-twiddling in step 49, I need one more step in order to be able to put the loop limit back into the program.

Re: Ongoing Pi Programming Contest Message #33 Posted by Paul Dale on 26 Oct 2008, 4:55 p.m., in response to message #31 by Katie Wasserman Quote: The need to multiply by a number up to log2(10) * number_of_digits means that several digits in each register are going to be wasted in order to avoid overflow. Has anyone considered the possibility of changing the word size during the computation? I.e. rcl the registers onto the stack, change the word size, do the operation, split the overflow and results, reset the word size and finally write things back. Just the kind of thing the 16c excels at. - Pauli

Re: Ongoing Pi Programming Contest Message #34 Posted by Katie Wasserman on 26 Oct 2008, 7:05 p.m., in response to message #33 by Paul Dale Yes, it is exactly what the 16C does so well. I had tried that in several different ways but it cost too many program steps and the net result wasn't advantageous. Kiyoshi is making a little progress in the same way that I got to 195 digits, by small optimizations. I think that an entirely different approach is needed to get much beyond 200 digits on the 16C. But it's the perfect calculator to experiment with.

Re: Ongoing Pi Programming Contest Message #35 Posted by Kiyoshi Akima on 26 Oct 2008, 7:28 p.m., in response to message #33 by Paul Dale Changing the word size during the computation doesn't work well for decimal computations. If the object were to get hexadecimal (or octal or binary) digits of pi, then all sorts of possibilities open up. But to satisfy the requirements of this particular challenge, converting from hex to decimal would require too much memory to be practical. I'm not saying it can't be done, only it would require more memory than doing it in decimal in the first place. I have to agree with Katie. I think we've gotten about as far as we can with this particular approach and algorithm. I also agree that the 16C is a great calculator with which to experiment. In fact, this was my answer to the HP vintage calculator survey (along with the 19C). I guess I'll have to spend some time with the 19C and see what I can do. Not much program memory, but lots of data registers...

Re: Ongoing Pi Programming Contest Message #36 Posted by Katie Wasserman on 26 Oct 2008, 7:43 p.m., in response to message #35 by Kiyoshi Akima I like the 19C quite a lot too. I haven't tried it yet with this algorithm, but with 100 steps I'm sure you'll be able to fit it all in and make use of all the registers except for a couple for internal variables. I think you'll get 189 decimal places and a nice printout of the result!

Re: Ongoing Pi Programming Contest Message #37 Posted by Paul Dale on 26 Oct 2008, 8:33 p.m., in response to message #30 by Kiyoshi Akima Quote: I'm not convinced the 56-bit wordsize is optimal. According to a quick calculation, 20-bit words have least waste when storing decimal digits (in this case 7 per word) in register lengths that are a multiple of 4-bits. 10-bit words would be better but they don't fit nicely into the nibble sized memory so they are out. 40-bit words are also pretty good. 56-bits is actually one of the worst. Well no, it is the worst. wsize max value #dig waste states 10 1024 3.0 0.023 20 1048576 6.0 0.046 40 1099511627776 12.0 0.091 56 72057594037927936 16.9 0.861 The waste being calculated as the number of "unused" binary states over the max value. - Pauli

Re: Ongoing Pi Programming Contest Message #38 Posted by Katie Wasserman on 26 Oct 2008, 9:02 p.m., in response to message #37 by Paul Dale Yes, but you're assuming that packing the maximum number of digits into a register is all that matters. There are practical considerations that dictate why I found 56 bits to be optimal for the algorithm used. Paramount among them is that using 13 decimal places within 56 bits allows for the right amount of "overflow" capacity that was needed for the arithmetic.

Re: Ongoing Pi Programming Contest Message #39 Posted by Egan Ford on 23 Oct 2008, 3:16 p.m., in response to message #27 by Kiyoshi Akima Hello Kiyoshi, You may find this useful: http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/articles.cgi?read=866. It's a "compiler" for the Nonpareil Voyager emulators. After changing line 23 to Rv, I had no problem compiling and running your code. Compiler options used: vcomp.pl comp -new 16C -nst 16C.nst -strip 8 pi.src I was able to run this on an accelerated 16C in about 5 minutes (described in the link above). The registers contained as expected: 3 1415926535897 9323846264338 3279502884197 1693993751058 2097494459230 7816406286208 9986280348253 4211706798214 8086513282306 6470938446095 5058223172535 9408128481117 4502841027019 3852110555964 4622948954930 3819644288109 With vcomp you can also pretty print your code, e.g.: vcomp.pl list -c 3 16C.nst 001 - 2 2 027 - F F 053 - 44 31 STO (i) 002 - C C 028 - 34 x<>y 054 - 1 1 003 - 4 4 029 - 43 3 x>y 055 - 22 9 GTO 9 004 - 43,22, b LBL B 030 - 22 d GTO D 056 - 43,22, F LBL F 005 - 44 .1 STO .1 031 - 1 1 057 - 0 0 006 - 0 0 032 - 40 + 058 - 43,22, 9 LBL 9 007 - 44 32 STO I 033 - 42 22 x<>I 059 - 43 23 DSZ 008 - 43,22, C LBL C 034 - 22 C GTO C 060 - 22 E GTO E 009 - 21 8 GSB 8 035 - 43,22, d LBL D 061 - 43,22, 7 LBL 7 010 - 20 x 036 - 2 2 062 - 45 31 RCL (i) 011 - 45 .1 RCL .1 037 - 44 0 STO 0 063 - 40 + 012 - 45 31 RCL (i) 038 - 45 .1 RCL .1 064 - 44 31 STO (i) 013 - 20 x 039 - 1 1 065 - 43 21 RTN 014 - 40 + 040 - 30 - 066 - 43,22, 8 LBL 8 015 - 36 ENTER 041 - 43 30 x>0 067 - 9 9 016 - 36 ENTER 042 - 22 b GTO B 068 - 1 1 017 - 45 .1 RCL .1 043 - 1 1 069 - 8 8 018 - 42 A SL 044 - 0 0 070 - 4 4 019 - 1 1 045 - 44 32 STO I 071 - E E 020 - 40 + 046 - 0 0 072 - 7 7 021 - 10 / 047 - 43,22, E LBL E 073 - 2 2 022 - 44 31 STO (i) 048 - 21 7 GSB 7 074 - A A 023 - 33 Rv 049 - 21 8 GSB 8 075 - 0 0 024 - 43 36 LSTx 050 - 30 - 076 - 0 0 025 - 42 9 RMD 051 - 43 2 x<0 077 - 0 0 026 - 42 22 x<>I 052 - 22 F GTO F vcomp.pl list -linecode -c 5 16C.nst 001 2 017 RCL .1 033 x<>I 049 GSB 8 065 RTN 002 C 018 SL 034 GTO C 050 - 066 LBL 8 003 4 019 1 035 LBL D 051 x<0 067 9 004 LBL B 020 + 036 2 052 GTO F 068 1 005 STO .1 021 / 037 STO 0 053 STO (i) 069 8 006 0 022 STO (i) 038 RCL .1 054 1 070 4 007 STO I 023 Rv 039 1 055 GTO 9 071 E 008 LBL C 024 LSTx 040 - 056 LBL F 072 7 009 GSB 8 025 RMD 041 x>0 057 0 073 2 010 x 026 x<>I 042 GTO B 058 LBL 9 074 A 011 RCL .1 027 F 043 1 059 DSZ 075 0 012 RCL (i) 028 x<>y 044 0 060 GTO E 076 0 013 x 029 x>y 045 STO I 061 LBL 7 077 0 014 + 030 GTO D 046 0 062 RCL (i) 015 ENTER 031 1 047 LBL E 063 + 016 ENTER 032 + 048 GSB 7 064 STO (i) Edited: 23 Oct 2008, 3:27 p.m.

Re: Ongoing Pi Programming Contest Message #40 Posted by PeterP on 23 Oct 2008, 4:44 p.m., in response to message #27 by Kiyoshi Akima Kiyoshi & Katie, Would you mind explaining the math behind your impressive concoctions to me or point me in the right direction to find out? Thanks a lot! Peter

Re: Ongoing Pi Programming Contest Message #41 Posted by Katie Wasserman on 23 Oct 2008, 11:05 p.m., in response to message #40 by PeterP Peter, Start here and look for "Using Euler's convergence improvement transformation gives". Since this series converges at a rate of one bit per iteration you need to iterate log2(10) * number of decimal digits, roughly. That's the outer loop. The inner loop is just the number of registers that you have to multiply and divide for each iteration. Overall the algorithm looks like: (N=number of digits, R=number of registers, D=number of digits/register) everything is an integer zero the registers r(1)=2 # not really needed since it will divide out to zero. for (i=log10(2)*N; i>=1 --i) {carry=0 for (j=1; j<=R; ++j) {x = r(j)*i + carry*10^D r(j) = x / (2*i+1)) carry = x % (2*i+1) } r(1)=2 # it really should be r(1)=r(1)+2, but it works out the same. } # Because the value in each register can be up to 2*10^D we need to fix that up by carrying into the next register. for (j=R; j>=1; --j) if (r(j)>=10^D) {r(j)=r(j)-10^D r(j-1)=r(j-1)+1 } -Katie Edited: 24 Oct 2008, 10:53 a.m. after one or more responses were posted

Re: Ongoing Pi Programming Contest Message #42 Posted by PeterP on 24 Oct 2008, 12:59 a.m., in response to message #41 by Katie Wasserman thanks a lot Katie, very instructive!! And now I have even a better appreciation for your programs! Cheers Peter

Re: Ongoing Pi Programming Contest Message #43 Posted by David Dyte on 24 Oct 2008, 6:40 p.m., in response to message #42 by PeterP There are some scary talented people here... - David D

[ Return to Index | Top of Index ]

Go back to the main exhibit hall