attempting to calculate e with spigot algorithm

This is a discussion on attempting to calculate e with spigot algorithm within the C Programming forums, part of the General Programming Boards category; Hello, everyone. I am trying to use a c program I found on the Internet: Code: int main(void){ int a[3302],b=3301,*c=a,d,e,f; ...

  1. #1
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11

    attempting to calculate e with spigot algorithm

    Hello, everyone. I am trying to use a c program I found on the Internet:

    Code:
    int main(void){
      int a[3302],b=3301,*c=a,d,e,f;
      for(e=b; --e; *c++=1)
          ;
      *c=2;
      for(d=2001; d--; printf("%05d",f)) {
        for(c=a, e=b; e; f/=e--){
          f += *c * 1e5;
          *c++ = f%e;
        }
      }
    }
    (I did insert an extra line at the end after the compiler complained about the lack of it.)

    I am trying to figure out why it does not seem to be giving me the right value for e. It did compile with some warnings but no fatal errors. The main warning were for the printf and for line 8 converting integer to floating point.

    Personally, I can say that I used to write c programs and fortran 77 programs when I studied at uCsD 1995-97 as well at mathlab at Pomona college 1994-5. But I'm a little rusty and I'm not that clear on what all the syntax is supposed to be doing: a[3302], *c, the single ; for line 4, printf("%05d",f) does what?, and lastly, *c++ = f%e; has % and I don't know what that does, again.

    I do have a basic grasp of the three for loops and what the basic math operations are doing, but without really understanding the program, I don't know how to adapt it to what I want to do, namely, to calculate even more digits of e (correctly, of course).

    It took me a few hours of looking around on the Internet to finally find a spigot algorithm that I could put into a computer language to try to calculate the base of natural logarithms. There were many formulas that produce e and various similar values (e^x, 1/e, etc), and I read that e has only been calculated out to a billion decimal places, so if the spigot algorithm could allow me to pick up where I leave off, then I can keep adding to my collection of digits.

    Help is greatly appreciated.
    Last edited by eehiram; 04-10-2006 at 12:31 AM.

  2. #2
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    868
    It gives the correct value of e, except without the decimal point. What value are you getting? The last few digits might be wrong, but that's a property of spigot algorithms in general.

    Also, the algorithm appears to be O(n^2) or worse, so you've very little chance of computing a billion digits using such a method.
    Last edited by cwr; 04-10-2006 at 02:29 AM.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    % is the modulus operator, which you can think of as taking the remainder after division.

    This code is very very very bad and ugly -- don't learn coding style from it!

    And it DOES seem to output the digits of e correctly.


    Listen to the warnings. They may signal possible runtime errors or bugs.
    If you want to get rid of the "convert double to int" warning, cast the double first:

    Code:
          f += (int)(*c * 1e5);
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  4. #4
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11
    The first line of output reads: 166650389113343-1859-4810-044205378-071015423-14763-505304262005271204801135-150

    What's the O(n^2) formula?

    Thanks for the pointers, Jafet. The point of this spigot algorithm is partly to be only 10 lines in length; one webpage has squeezed it down to a double line, but without line breaks of course.

  5. #5
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11
    The only remaining error states that printf "function declared implicit int". I tried adapting your (int) suggestion, but it doesn't seem to have the right effect on my compiler.

  6. #6
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    868
    I get 27182818284590452353602874713526624977572470936999 59574966967627724076630353...

  7. #7
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11
    Well, cwr, I'm not sure what the problem is because I copied and pasted my code into this forum in my original post, so it's not the code itself. Maybe it's a glitch in my compiler.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,453
    Sure, blame the compiler - nice of you not to state which one that is....

    > The point of this spigot algorithm is partly to be only 10 lines in length
    How about blame the code? Terse, but wrong is still wrong.


    First attempt at compiling your code
    Code:
    $ gcc -W -Wall -ansi -pedantic -O2 foo.c
    foo.c: In function ‘main’:
    foo.c:4: warning: ‘f’ may be used uninitialized in this function
    OK, fix that problem, try again
    Code:
    $ gcc -W -Wall -ansi -pedantic -O2 foo.c
    $ ./a.out
    271828182845904523536 yada yada yada
    My guess is your compiler doesn't initialise 'f' to zero like the code expects.
    int a[3302],b=3301,*c=a,d,e,f=0;
    Not that it's obliged to initialise it to anything at all unless you say so.
    So if it works at all for some people, that's just one happy coincidence.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11
    Well, Salem, the code still does work. Here is my version, copied and pasted:

    Code:
    int main(void){
      int a[3302],b=3301,*c=a,d,e,f=0;
      for(e=b; --e; *c++=1)
          ;
      *c=2;
      for(d=2001; d--; printf("%05d",f)) {
        for(c=a, e=b; e; f/=e--) {
          f += (int)(*c * 1e5);
          *c++ = f%e;
        }
      }
    }
    It seems to be working for other people here on this board, although not without some disapproval at the method of calculation.

    My compiler is a freeware compiler I got from www.htsoft.com/products/PACIFICc.php. It seems to be old because the minimum requirement is an 80286 and it does not support ms windows, but I didn't want to spend the money on a compiler yet.

    The reason is that I was first going to try to write my calculation programs in java 1.5. But looking around on the Internet, I did not find code ready to go for java 1.5 to calculate e; I only found it for c.

  10. #10
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11
    Here is one website with the above code: http://www.matpack.de/Info/Mathematics/Pi.html

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,453
    > My compiler is a freeware compiler I got from
    Yes, it is old, and as such it's int's are 16-bit rather than 32 bit.
    When I change my version to use 16-bit integers, it all goes horribly wrong as well.

    Try a 'long' version which should result in 32-bit numbers for your fossil compiler.
    Code:
    #include <stdio.h>
    int main(void){
      long int a[3302],b=3301,*c=a,d,e,f=0; /* added long */
      for(e=b; --e; *c++=1)
        ;
      *c=2;
      for(d=2001; d--; printf("%05ld",f)) { /* added l to the format */
        for(c=a, e=b; e; f/=e--){
          f += *c * 1e5;
          *c++ = f%e;
        }
      }
      return 0;
    }
    > but I didn't want to spend the money on a compiler yet.
    Dev-c++ seems to be the free compiler of choice.
    http://www.compilers.net/
    http://www.thefreecountry.com/compilers/cpp.shtml
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Dev-C++ is not a compiler, it's an IDE. It uses the MinGW compiler package.

    Homepage
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  13. #13
    Registered User
    Join Date
    Apr 2006
    Location
    Encinitas, CA 92024
    Posts
    11
    I think the 16 bit int vs. 32 bit int seems to explain the discrepancy. For now, I don't have the money to put up for a new c compiler, or even a 2002 c compiler for that matter. So, I throw in the towel now.

    Thanks to everyone for trying to help me out; maybe I'll be back in a year.

    For now, I'm going to look for spigot algorithms to write up in Java 1.5.0.

  14. #14
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    You don't need money; gcc (and Dev-C++) is 110% free of charge. It complies to current standards.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Small program that has to calculate miles per gallon
    By Guti14 in forum C++ Programming
    Replies: 6
    Last Post: 01-06-2004, 01:47 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21