mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2009-09-30, 23:34   #1
Unregistered
 

11100011000012 Posts
Default Easy Question

I'm a complete noob when it comes to programming in c, but you have to start somewhere. I ran into a question about factorials. Can you use "n!"? It didnt work for me, I instead went about it the long way,

# include <stdio.h>

int main (void)
{

int n, n1 = 1, n2 = 2, n3 = 3, n4 = 4, n5 = 5, n6 = 6, n7 = 7, n8 = 8, n9 = 9, n10 = 10, nResult;

printf("-n- -n!\n\n");


printf( "%i %2i\n" , n1 , nResult = n1);
printf( "%i %2i\n", n2, nResult = n1 * n2);
printf( "%i %2i\n", n3, nResult = n1 * n2 * n3);
printf( "%i %2i\n", n4, nResult = n1 * n2 * n3 * n4);
printf( "%i %2i\n", n5, nResult = n1 * n2 * n3 *n4 * n5);
and so on....
}


Whats an easier way?
  Reply With Quote
Old 2009-10-01, 00:06   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

http://montcs.bloomu.edu/~bobmon/Code/C/two-factorials.shtml
Mini-Geek is offline   Reply With Quote
Old 2009-10-01, 11:48   #3
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

26·3·17 Posts
Default

In case the methods in Mini-Geek's link are too advanced for the moment, here a few comments which might help you improve your own program:

- It's neater and more generic to have a counting variable to which you add one each time instead of storing 1, 2, 3, ... in individual variables. Then instead of recalculating n1*n2*n3*... from the start in each step it would be more efficient to hold each intermediate result (1, 2, 6, 24, ...) in a variable and multiply that variable by the counting variable each time. So when you have reached 4!=24 you add one to the count and multiply 24 by the new count of 5 to get the next result. You will need to write a loop (hint: for, while or do).

- Your integer variable nResult will soon overflow. (The examples in Mini-Geek's link don't take this into account either!) You could test to see if overflow has occurred at each stage (hint: try dividing back and see if you get the previous answer) and stop when this happens. If your compiler supports the "long long" type you can continue the process a bit further than with ordinary integers.

Last fiddled with by Brian-E on 2009-10-01 at 12:24
Brian-E is offline   Reply With Quote
Old 2009-10-01, 13:03   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Unregistered View Post
I'm a complete noob when it comes to programming in c, but you have to start somewhere. I ran into a question about factorials. Can you use "n!"? It didnt work for me, I instead went about it the long way,

# include <stdio.h>

int main (void)
{

int n, n1 = 1, n2 = 2, n3 = 3, n4 = 4, n5 = 5, n6 = 6, n7 = 7, n8 = 8, n9 = 9, n10 = 10, nResult;

printf("-n- -n!\n\n");


printf( "%i %2i\n" , n1 , nResult = n1);
printf( "%i %2i\n", n2, nResult = n1 * n2);
printf( "%i %2i\n", n3, nResult = n1 * n2 * n3);
printf( "%i %2i\n", n4, nResult = n1 * n2 * n3 * n4);
printf( "%i %2i\n", n5, nResult = n1 * n2 * n3 *n4 * n5);
and so on....
}


Whats an easier way?
Let me start by asking: Are you a novice programmer in general?

You do realize that the multiplication of two integers can overflow?

Do you know how to code recursive functions in any language (i.e. not
specifically C?). If not, may I assume that you at least know how to
code a simple loop?

Do you have any understanding of multi-precision arithmetic?

Aside from the issue of the choice of programming language, may
I suggest that you read about coding arithmetic algorithms? Start
with Knuth "The Art of Computer Programming", vol 2.

There are many issues involved in coding n! that are separate from the
choice of coding language.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-01, 16:33   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts
Default

Here's an example in Java that uses BigInteger, an arbitrary-precision integer, and prints every factorial up to the size you specify:
Code:
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        factorialWithBigIntNoDiv(100);
    }

    public static void factorialWithBigIntNoDiv(long n) {
        BigInteger fact = BigInteger.ONE;
        for (BigInteger i = fact; i.compareTo(BigInteger.valueOf(n)) <= 0; i = i.add(BigInteger.ONE)) {
            fact = fact.multiply(i);
            System.out.println(i + "! = " + fact);
        }
    }
}

Last fiddled with by Mini-Geek on 2009-10-01 at 16:34
Mini-Geek is offline   Reply With Quote
Old 2009-10-01, 17:09   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,483 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Start with Knuth "The Art of Computer Programming", vol 2.
Allow me to disagree.

Knuth is excellent, and his "The Art of Computer Programming" is a treasure for the ages. But a beginning programmer should start from something simpler and work up to TAoCP. Its size and cost are likely to discourage!
CRGreathouse is offline   Reply With Quote
Old 2009-10-01, 17:18   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·61·83 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Allow me to disagree.

Knuth is excellent, and his "The Art of Computer Programming" is a treasure for the ages. But a beginning programmer should start from something simpler and work up to TAoCP. Its size and cost are likely to discourage!
Seconded.

TACP is an excellent text. Everyone except (many) novice should own a copy and study it carefully. My cop is well-thumbed, is falling apart from use, and I've learned a lot from it.

That said, it's probably not the first port of call for most programmers. Second, definitely.


Paul
xilman is offline   Reply With Quote
Old 2009-10-01, 20:24   #8
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Here's an example in Java that uses BigInteger, an arbitrary-precision integer, and prints every factorial up to the size you specify:
Maybe the answer the O.P. was looking for is rather something like
Code:
int factorial(int n){ int f=1; while( n>1 ) f *= n--; return(f); }

main(){ int n; for( n=1; n<10; n++ ) printf( "%d ! = %d\n", n, factorial(n)); }
Of course I know that I could have used "unsigned long long" or mpz instead of "int" in factorial, but w.r.t. n1=1; n2=2; ... it should be just perfect as is.
m_f_h is offline   Reply With Quote
Old 2009-10-01, 21:40   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Allow me to disagree.

Knuth is excellent, and his "The Art of Computer Programming" is a treasure for the ages. But a beginning programmer should start from something simpler and work up to TAoCP. Its size and cost are likely to discourage!
The subject at hand is the coding of arithmetic algorithms.

Do you have a better book? Rivest et al? Aho, Hopcroft, Ullman?
Sedgwick? I was not suggesting a general text about coding, but
rather one that discusses numerical algorithms and the (multi-precise)
arithmetic involved in computing/coding n!
R.D. Silverman is offline   Reply With Quote
Old 2009-10-01, 22:04   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,483 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I was not suggesting a general text about coding, but
rather one that discusses numerical algorithms and the (multi-precise)
arithmetic involved in computing/coding n!
I don't think the OP needs to read a book about numerical algorithms to discover how to program the factorial function in C. I think a quick pointer on recursive algorithms or loops would be better.

Quote:
Originally Posted by R.D. Silverman View Post
Do you have a better book? Rivest et al? Aho, Hopcroft, Ullman? Sedgwick?
If the OP was really looking for a book, I would sooner recommend Yan's Number Theory for Computing as its level is more appropriate. But I don't think any book is needed here, unless perhaps a text on introductory programming.
CRGreathouse is offline   Reply With Quote
Old 2009-10-02, 01:19   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I don't think the OP needs to read a book about numerical algorithms to discover how to program the factorial function in C. I think a quick pointer on recursive algorithms or loops would be better.



If the OP was really looking for a book, I would sooner recommend Yan's Number Theory for Computing as its level is more appropriate. But I don't think any book is needed here, unless perhaps a text on introductory programming.
Perhaps I am giving the OP too much credit, but he did not say that
he was a novice programmer; only that he was a novice with C.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Manual Results Question ... an easy one. petrw1 PrimeNet 7 2013-08-14 13:54
A probably easy question about PFGW and twins Puzzle-Peter Twin Prime Search 0 2011-06-25 07:41
4 not so easy pieces? Uncwilly Puzzles 35 2006-11-15 01:07
Another easy one fetofs Puzzles 10 2006-11-03 03:29
Easy Mini-Geek Puzzles 3 2006-10-19 17:14

All times are UTC. The time now is 15:26.

Wed Oct 28 15:26:54 UTC 2020 up 48 days, 12:37, 3 users, load averages: 2.10, 1.79, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.