500!

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

barhoooooom - 06 Jul 2004 23:07 GMT

ben...happy birthday.. ;) am I invited to the party ;)

I am sorry to tell you that I could'nt make a lot of benifit out of the
link you gave me, thanks any ways..

tom....thanks for your concern, I have thought of that before writing
my code, but I was too lazy to try to write it and c how fast it is. it
is actualy still not fast( I think so) any ways, I will try it.

tom, ben, carl, william and every one else...I have found on a site a
solution for this problem, and it is pretty fast, I have tried it for
1000! and in a second I got the answer, for 10 000 I got it in about a
minute, for 100 000 I couldn't get an answer for hours. any ways it is
a very very very satisfactory spead, since I need only upto 1000!

the problem now is: I CANT UNDERSTAND THE CODE :(

here is the link:
[url]http://www.codeguru.com/Cpp/Cpp/algorithms/factorials/article.php/c2041/[/url]

he has created a list similar to the STL deque I am using, and then in
main...I just got dizzy from following the loops and couldn't get what
he is doing. NO COMMENTS IN THE CODE, now I understand why my proff
taks marks out for not commenting the code....

anyways, any help with the code? I just want to know what he is
doing...I'd really appreciate any help

okays....thanks...and ....I am waiting

Reply to this Message

tom_usenet - 07 Jul 2004 12:46 GMT

>ben...happy birthday.. ;) am I invited to the party ;)
>
[quoted text clipped - 4 lines]
>my code, but I was too lazy to try to write it and c how fast it is. it
>is actualy still not fast( I think so) any ways, I will try it.

It is fast - it is O(n log n) I think (or maybe O(n*n)). It's also
roughly how the version below works.

>tom, ben, carl, william and every one else...I have found on a site a
>solution for this problem, and it is pretty fast, I have tried it for
[quoted text clipped - 14 lines]
>anyways, any help with the code? I just want to know what he is
>doing...I'd really appreciate any help

The algorithm is just multiplying each digit of the current total by
the current factor (starting from the least significant), and working
out the new value of the digit (which is in base 10) and the carry
over to the next higher digit. It's similar to the way you were taught
to do multiplication with a pen and paper at school. I could post the
code (with std::deque it's a lot shorter), but I think you should have
a go at coding the algorithm yourself first.

Using std::deque or std::vector, 10000! should take only 4 or 5
seconds on a 2+ GHz machine (from a quick test I knocked up).
std::list doesn't take much longer (though it requires 1 memory
allocation per digit of the result).

Tom

Signature

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

Reply to this Message

Rate this thread:

500!

Free Magazines