From voyageur@sky.net Thu Dec 25 12:31:29 1997 Date: Fri, 19 Dec 1997 14:22:06 -0600 From: Mark Andreas To: jasonp@isr.umd.edu Subject: TinyPI I've optimized the TinyPI program on your webpage, reducing its size from 125 bytes down to 116, even though I don't understand how it works. If interested, I can send you a corrected version of your http://www.isr.umd.edu/~jasonp/pi_com.uu page. I did notice that your page has a typo on it. The TinyPI shows a "MOV BX,32654". As you can see, this is different from the "MOV CX,32564" shown earlier. The BX value should be changed to 32564. I haven't been able to find any sources which explain why the number 14 is used in the code. I wish to adapt the program to output hex digits of PI, but can't get it to work correctly. i.e. PI in hex begins with 3.243f6a88... From voyageur@sky.net Thu Dec 25 12:31:37 1997 Date: Fri, 19 Dec 1997 16:25:03 -0600 From: voyageur@sky.net To: Jason Stratos Papadopoulos Subject: Re: TinyPI At 04:31 PM 12/19/1997 -0500, you wrote: >Wonderful! I'd be grateful if you can pass a copy my way. I don't have my ASM code ready for "prime-time" yet, I'll send soon when it's ready. I was hoping I'd be able to have hex and decimal versions ready - but as you can see, I'm having trouble with the hex. >You're probably having trouble converting the output to hex because >the program works internally in decimal. The *only* thing you need to do >in order to change to binary internally is intead of multiplying by >10000, multiply by 32768. This not only allows you to pack more digits >into a single word, but to print it out you just use the value of the >register directly. I'd appreciate it if you could send me pseudocode for getting the output in hex. Here's what I've found so far for generating decimal digits: #include long a=10000,b,c=2800,d,e,f[2801],g; main() { for(;b-c;)f[b++]=2000; for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a) for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b); } This is the same as the calculate-pi.c that is found at various FTP sites, except above changes the a/5 to 2000, and the variables are carried as long's instead of being int's. For changing output to hex, I changed the "%.4d" into "%.4x". I tried your suggestion of changing a=32768, but that didn't work either. I had already tried changing a=65536, but that didn't work either. I've tried changing the f[] array's initial value back to a/5, but that didn't work either. I assume you said 32768 instead of 65536 because of C wanting to use signed values. The best I've been able to do is get output beginning with 0x0c45, which is hex for 3141 decimal, but that's not close to the 3.243f6a88... value I was looking for. >If you don't care about making the program twice as slow, and don't mind >waiting until the calculation is finished before printing anything, then >you can probably reduce the code size significantly and double the number >of digits allowed by memory if you instead compute > >pi = 2 + 1/3*( 2 + 2/5*( 2 + 3/7*( 2 + 4/9*( 2 + ...)))))))))...) > >because this way you just race through one single array over and over >again instead of modifying another array and adding it on. The drawbacks >are that 1) you have to know how many terms to add up in advance, because >you start at the last term and work backwards, and 2) the computation >doesn't speed up as time goes on; you must always use the full size array, >and this doubles the computing time. In addition to the drawback of having this new version take twice as long, another drawback would be that there's no display until the program is ready to spit out everything. If it takes several minutes on someone's slower computer, they may think their computer froze. At 02:12 AM 12/20/1997 -0500, you wrote: > >Well, I think your problem with assembly is beyond my skills. Isn't >there a dos interrupt that prints a register value in hex? There are >certainly enough interrupts to do *other* things. Maybe you can find >the source to C's printf() function (should be publicly available >somewhere, like the source for the DJGPP compiler). I'm not having trouble with the assembler part, I was having trouble getting the correct hex output from either the C or ASM version. I assumed you were more familiar with C, so I included the C code which outputs the decimal PI digits, and is the C equivalent of the TinyPI ASM code. As you can see, the C code I sent produces the correct decimal output beginning with 31415926. Using your suggestion of changing the "A" value to 32768 (and changing the printf string to "%.4x"), you can see that the code produces hex output which begins with 0x0c45, when the hex value of PI actually begins with 3.243f6a88. I was hoping it would be easier for you to explain what modifications were needed to obtain the correct hex output if I gave you the C equivalent to TinyPI. I'm still looking at your modified version's code, but I'm worried that if the normal version can't be modified to output hex digits, that perhaps the modified version would end up with output similar to the 0xc45 output. I've made a few more changes to TinyPI, and have the program size down to 113 bytes. To: Jason Stratos Papadopoulos Subject: Re: TinyPI > Well, I fooled around a little with the problem. The following C code > produces the correct result in hex; note that I made two mistakes in > what I told you; the first was that you really should use 65536 as > the multiplier, and the second has to do with the initial value of > the remainder. [NOTE: the program in question was : --------------------------------------------------------------------- #include int main(void) { unsigned short size=100, array[100]={0}, denom, remainder, terms; int i; unsigned long dividend; terms = 1600; denom = 2*terms+1; while(terms>0) { remainder = denom - 1; for( i=0; i I have no idea how to modify the C program you passed on; it compiled > but wouldn't run at all, and I can't follow the code itself. This is strange, as it compiled for me just fine. Perhaps it's due to your using a different compiler, similar to the problem of the program putting out 0's at first. The output looked good at first, but it appears that there is a slight error creeping in. I actually prefer not having the 3 at the beginning, and suspect that it's not there because the array is initialized with 0, instead of with 2000 as the program on your page does. The program outputs these digits: 243f6a8885a208d213198a2d03707344a4093822 299f31cf082efa98ec4e6c89452821e638d01377 be5466cf34e80c6cc0ac29b7c97c50dd3f84d5b5 b54609179216d5d98979fb1bd1300ba698dfb5ac 2ffd72dbd01adfb7b8e1afed6a267e96ba7c9045 f12c7f9924a19947b3916cf60801f2e2858efc16 636920d871574e69a458fea3f4933d7e0d95748f 728eb658718bcd5882154aee7b54a41dc25a59b5 9c30d5392af26013c5d1b023286085f0ca417918 b8db38ef8e79dcb0603a180e6c9e0e8bb01e8a3e ... but the first 400 hex digits of PI are actually: 243f6a8885a308d313198a2e03707344a4093822 299f31d0082efa98ec4e6c89452821e638d01377 be5466cf34e90c6cc0ac29b7c97c50dd3f84d5b5 b54709179216d5d98979fb1bd1310ba698dfb5ac 2ffd72dbd01adfb7b8e1afed6a267e96ba7c9045 f12c7f9924a19947b3916cf70801f2e2858efc16 636920d871574e69a458fea3f4933d7e0d95748f 728eb658718bcd5882154aee7b54a41dc25a59b5 9c30d5392af26013c5d1b023286085f0ca417918 b8db38ef8e79dcb0603a180e6c9e0e8bb01e8a3e The 3rd 4-digit value is output as 85a2, but should actually be 85a3. I thought there might be some sort of rounding error, except the wrong digit is only sporadic. Only 9 of the first 400 digits are wrong. [NOTE: this is because if you try to do too much at once you wind up with quotients more than 16 bits in size, and my original program had no provision for carries -JP] > PS: I'm a little surprised that you can get away with only one > array in the original program; the math behind it is probably > pretty easy though. I don't completely understand how the TinyPI program is working, but I see parts of it that are similar to your code. Unfortunately, a miss is as bad as a mile, so I can't make a tiny-hex version based on your C program until the errors have been removed. If you can verify that your program outputs correct data, I'll have to blame it on my C compiler. If you could help eliminate those last few digit errors, I would really appreciate it.