473,322 Members | 1,522 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

500!


hello, hows life? mine is good ;)

as I was surfing the net, I found a little question, it wants a progra
that gets the factorial of any number only less than 1000....you kno
what is 30! ...? it is simply 2.6525285981219105863630848e+32

so if I am going to get 500! or maybe 1000! then you can imagine ho
big the number is.

I thought of using an array whose elements are the digits of my bi
number, then write a function that adds two big numbers, then agai
write another function that multiplies two big numbers using th
addition function.

then just use this function in the famous factorial recursiv
solution.

it is a very stupid solution, very stupid and illogical, because...
wrote the addition and multiplication functions, and as I tried t
multiply 1000*1000, it took about 2 full long seconds, then again fo
10000*10000 it took about 20 seconds.

this is stupid, because I am not even yet using a big number, usin
long int I can get the answer of this in less than a second. s
imagine what happens when I get 500! wow, dont want to think.

any ways, here is my code,

* if you have any optimizations to the additiona and multiplicatio
functions, then please point them out, I thought of passing the resul
as a reference instead of returning it every time, but I can't think o
more performance optimizations.

* if you have a better way for manipulating huge numbers then pleas
point it out (in C++ only ofcourse not java)

* if you have a solution for this 500! problem then please, I'd like t
know it.

I am not sure if any one will bother read my long email and help me ge
1000! ....!! I'll just throw the question in this forum. hope some on
does

copy and paste it please into your compiler before reading it.

#include <iostream>
#include <deque>
#include <string>
using namespace std;
/************************************************** ********************************/

/* functions to be used in the program */
void getBigNum(deque<int> &);
void outBigNum(deque<int> &);
deque<int> addBigNum(deque<int> &, deque<int> &);
deque<int> multiplyBigNum(deque<int> &, deque<int> &);
/************************************************** ********************************/

int main()
{
//the big numbers are stored as deques of intacters
deque<int> BigNum1;
deque<int> BigNum2;
deque<int> answer;
// get the big numbers from the user
getBigNum(BigNum1);
getBigNum(BigNum2);

outBigNum(BigNum1);
cout << "*";
outBigNum(BigNum2);
cout << " = ";

//multiply the two big numbers and output the result
answer = multiplyBigNum(BigNum1, BigNum2);
outBigNum(answer);
cout<<endl;
return 0;
}
/************************************************** ********************************/


/************************************************** ********************************/
//get the big integer from the user
void getBigNum(deque<int> & num)
{
string temp;
cin >> temp;

for(int i=0; i<temp.size(); i++)
num.push_back(temp[i]-48);
}
/************************************************** ********************************/

/************************************************** ********************************/
// output the big number
void outBigNum(deque<int> & num)
{
for(int i=0; i<num.size(); i++)
cout << num[i];
}
/************************************************** ********************************/


/************************************************** ********************************/
//add two big numbers and return the result
deque<int> addBigNum(deque<int> & n1, deque<int> & n2)
{
int MAX;

//give MAX the size of the larger number
if(n1>n2 && n1.size()>=n2.size())
MAX=n1.size();
else
MAX=n2.size();

deque<int> result(MAX+1), carry(MAX+1), num1(MAX+1), num2(MAX+1);

//initialize the new deques to 0;
for(int i=0; i<=MAX; i++)
{ carry[i]=0; num1[i]=0; num2[i]=0;}

//copy n1 into num1 with leading zeroes if it is the smaller in size
for(i=0; i<n1.size(); i++)
num1[MAX-i] = n1[n1.size()-i-1];

//copy n2 into num2 with leading zeroes if it is the smaller in size
for(i=0; i<n2.size(); i++)
num2[MAX-i] = n2[n2.size()-i-1];

int sum;

/*********** here goes the addition ***********/
for(i=0; i<=MAX; i++)
{
sum = num1[MAX-i] + num2[MAX-i] + carry[MAX-i];

if( sum < 10)
result[MAX-i] = sum;
else
{
result[MAX-i] = (sum) - 10;
carry[MAX-i-1]=1;
}
}

//remove the unnecessary 0 if it exists
if(result[0]==0)
result.pop_front();

return result;
}
/************************************************** *******************************/



/************************************************** ********************************/
//multiply two big numbers and return the result
deque<int> multiplyBigNum(deque<int> &n1, deque<int> &n2)
{
deque<int> counter(1), result, one(1);
counter[0]=1;
result=n2;
one[0]=1;

while(counter.size()!=n1.size() || counter<n1)
{
result = addBigNum(n2, result);
counter = addBigNum(counter,one);
}
return result;
}
/************************************************** ********************************/

--
barhoooooom
------------------------------------------------------------------------
Posted via http://www.codecomments.com
------------------------------------------------------------------------

Nov 17 '05 #1
3 1734
"barhoooooom" <ba****************@mail.codecomments.com> wrote in message
news:ba****************@mail.codecomments.com...
it is a very stupid solution, very stupid and illogical, because... I
wrote the addition and multiplication functions, and as I tried to
multiply 1000*1000, it took about 2 full long seconds, then again for
10000*10000 it took about 20 seconds.


Someone may help solve the problem you posed.

If no one does, you may want to search the net for one of the "big integer"
libraries on the net. As the numbers used in strong cryptography often have
thousands of bits, you can use a library to keep from reinventing the wheel.

Regards,
Will
Nov 17 '05 #2
barhoooooom wrote:
hello, hows life? mine is good ;)

as I was surfing the net, I found a little question, it wants a
program
that gets the factorial of any number only less than 1000....you know
what is 30! ...? it is simply 2.6525285981219105863630848e+32
How do you want the answer expressed? In particular, do you want a decimal
representation, or would a binary representation be sufficient?

If you want decimal, then you're probably best off doing the entire
calculation in decimal, otherwise you can do the calculation in binary.
Converting a very large binary number to decimal involves implementing
large-number division, which is rather slow and tricky compared to
multiplication.
I thought of using an array whose elements are the digits of my big
number, then write a function that adds two big numbers, then again
write another function that multiplies two big numbers using the
addition function.
That's O(N*M) complexity so it's going to tend to be slow alright!

then just use this function in the famous factorial recursive
solution.

it is a very stupid solution, very stupid and illogical, because... I
wrote the addition and multiplication functions, and as I tried to
multiply 1000*1000, it took about 2 full long seconds, then again for
10000*10000 it took about 20 seconds.


You must have missed some optimizations - after all, when you learned in
school how to multiply 1000*1000, you didn't add 1000 to an accumulator 1000
times...

A key observation for this particular problem is that for any pair of
numbers you're trying to multiply, one of the numbers will be "small" (<=
1000) and one of the numbers will be "large" - possibly quite large.
Presumably since you went to the trouble you did, you're looking for an
exact result of n!, not a floating point approximation.

-cd
Nov 17 '05 #3
> hello, hows life? mine is good ;)

it's my birthday :)
as I was surfing the net, I found a little question, it wants a program
that gets the factorial of any number only less than 1000....you know
what is 30! ...? it is simply 2.6525285981219105863630848e+32 [...] then just use this function in the famous factorial recursive
solution.


perfwise this is not the best solution. have a look at

http://www.luschny.de/math/factorial...lFunctions.htm

also gives code examples (in c# and java)

hth
ben
Nov 17 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Mark Smithers | last post by:
Hi All, I'm having a frustrating time trying to debug an ASP (not ASP.NET) app on my W2003 dev server running II6. I continually get a HTTP 500 error message despite configuring IIS 6 to...
32
by: Rich | last post by:
I'm sure it sounds kinda nutty to display 200 columns and 500,000 rows of data. But I have been pulling data from a Lotus Notes database into Sql Server for a while now, but Lotus Notes is...
5
by: Ben | last post by:
hi when I try to excecute an ASP (either JS or VB) script to say, access a database record, I get an Internal Server Error HTTP 500.100 Why? and HOW CAN I FIX THIS? Thanks
4
by: reo | last post by:
if I put in a pagina asp the instruction: server.scripttimeout=1 the page indeed expires immediately, but the error that produces does not get to happen through 500-100.asp some solution, since...
1
by: slugger | last post by:
Hope this is not OT: I am running into some strange things whenever my ASP pages send out simultaneous requests to another ASP page which in turn gains access to a MySQL database using a DSNless...
2
by: James | last post by:
Hi, I am using Visual C++ 6.0. I got a "stack overflow" error message when running the program because of a "double array". I have a computer with 1GB memory. Can I extend the memory for the...
3
by: Jesse Napier | last post by:
I have a customerrors section in web.config something like the following: <customErrors mode="On" defaultRedirect="/errorPage/errorpage.aspx" > <error statusCode="404"...
6
by: Damien Sawyer | last post by:
Hello - I'm having a serious problem with IIS on Windows XP pro. Whenever I try to run ASP pages, I get HTTP 500 - Internal server error This behaviour happens identically, on two 'totally...
8
by: Rod | last post by:
I have been working with ASP.NET 1.1 for quite a while now. For some reason, opening some ASP.NET applications we wrote is producing the following error message: "The Web server reported...
5
by: jegec | last post by:
Hi all! Brief subject: I have to develop an ASP-based application, and build also a specific error handling ASP. After that I had set the virtual directory Custom Error 500;100 to new ASP -...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.