Printable View
Shouldnt computers be able to multiply and add numbers what ever their size is? How to add extremely large numbers?
for example, im tryig to solve this
but I cant find the value of 100! because its too large and VB cant multiply such large numbers... what's the solution? how to do this big calculations?Quote:
n! means n × (n − 1) × ... × 3 × 2 × 1
Find the sum of the digits in the number 100!
What are you declaring it as? A Long datatype should be able to hold value up to a trillion trillion or something like that.
The computer is limitted to the size of the largest number it can handle. Since you really need to stick to integers for this, the largest integer is 2^63, which is the size of a Long. I don't know how big 100! is, but if it is larger than that, the process you will need to go through to handle the larger number can become very tricky.
One thing that might work would be to use the Decimal data type, and shift the decimal places of all your numbers by 1, such that you are actually multiplying 10 x 9.9 x 9.8 x 9.7 x etc. Whether or not there would be any rounding errors would be a real question, and I don't know the answer. The resulting number would be considerbably smaller than the size of an integer, but you would need all of the decimal places to be correct (a double simply wouldn't do because the decimal places would NOT be correct). If the decimal places are correct, you sum all the digits, and ignore where the decimal point actually ended up.
The alternative is a difficult chore of holding multiple Long values, and checking each multiplication to see whether it was too large for the low Long, and if it is, manually moving it to the high Long. This would be VERY complicated, but it is doable.
100 ! = 9.33262154 × 10157 = about 9 × 10157
2^63 = 9223372036854775808 = about 9 × 1018
A considerable difference I would say :p
So 100! is a number with 158 digits.
The sum of 158 seperate digits can never exceed 158 * 9 (9 + 9 + 9 + 9 + ... 158 times), which is only 1422.
So the problem is obviously not the actual sum of the digits, it's finding the digits in the first place that's the hard part.
I have no idea how to be able to do that without actually calculating it directly (100 * 99 * 98...) which is impossible, at least with VB or probably with any computer :p
There are certainly other ways to do it, but sadly I don't know them.
Well, I ran a test on this and the good news is that VB can handle the processing up to the number 20. That means you'd only have to multiply 80 more using a pen and paper.
Maybe this can help:
http://www.rain.org/~mkummel/stumpers/28jan00a.html
It deals with calculation 100! using BASIC which is similar to VB.
The website also shows the actual number, but that's not what i posted this for, try to get it yourself ;)
Ok, using a Long is out of the question. That leaves the two alternatives I mentioned.
Also, after further thought, and seeing how big 100! actually is, the old method of spreading the number across multiple longs, while possible, would be more tricky than I thought. Very quickly, the amount being added in would have to fit across multiple Longs itself, and adding two such numbers gets interesting. You'd want to make an ExtremeLong class that was capable of holding a number as big as 100!, then you would have to add a Copy constructor, and an addition method that would each take an ExtremeLong object. Technically, the math behind that class wouldn't be all that challenging. The low Longs would be compared, and if they would exceed the size of a Long when added, then the new low Long would be set to the remainder, and the next highest Long would be incremented. Then the same process would have to happen for the next set of Longs, and soforth until the addition is complete. Using a List (of Long) could make for a class that can handle integers of any size.
To do the 100!, you would also have to implement a multiplication method, which would be FAR more complicated, or else you would have to recognize that 100 x 100 is the same as 100+100+100....etc. 100 times over. Thus, any multiplication can be done using addition in a loop. I guess that would be the basis of a simple multiplication method.
It would actually be a very interesting (and largely useless) exercise to write an InfiniteInteger class in that fashion.
When it comes to large number factorials, you could use approximation formulas. One of the names that grazed my ear as I was dozing in my maths class is Stirling's formula.
n! = (√(2*pi*n)) * (nn/en)
When you want to sum the digits in a number, approximations are only approximate.
More or less, somewhat, about right, yes. :afrog:Quote:
Originally Posted by Shaggy Hiker
Create your own HugeInteger class (or you can Google for "Huge Integer VB.Net" and there's a good chance that someone has already done it for you). If you still can't find it, I'll be glad to help with writing such a class.
I read a similar question somewhere before. The poster said he wrote his factorial program in VB.NET and failed because it couldn't go over 90! or there abouts, while a fellow student used Java and passed because Java has a BigInteger type that can handle very large numbers. Given that that is a language limitation I think it was very harsh that the teacher failed that student.
I should also point out that the Java BigInteger is NOT like other numerical types. In VB an Integer is a single 32-bit memory location. The Long type is two memory locations combined to make a 64-bit field. Java numeric types would be basically the same. Because these numeric types have a fixed size they are inherently limited in what values they can contain. I'd imagine that we will be graced with an Int128 type in the .NET Framework sometime in the future, but not yet.
Now, the Java BigInteger type is NOT just a wider field. If it was it would also have size limitations. The BigInteger type would use 32-bit values internally and soem jiggery-pokery to work it's magic. There is no similar type in the .NET Framework but I too thought that maybe someone else had already implemented the like in a .NET language, so I went looking back when I saw that other post. Alas, I found nothing.
It would be eminently do-able, but it's not something I'd relish being assigned. That said, you could always reference the Java class library provided via the J# redistributable. J# was canned after 2005 but you should still be able use the 2005 version. You can then use the Java BigInteger type in your .NET apps. The drawback is that your app would then require the standard .NET Framework and the J# redistributable to be installed in order to run.
i didnt find any already done classQuote:
Originally Posted by stanav
i found something called HIME but
A huge integer number in HIME can be hundreds of millions of digits long; 2^31 (2147483648) bits long. MILLIONS of decimal digits!
its still under 100!
the only option left is creating my own HugeInteger class ...?
where should i start to be able to create such a class?
I used to have a dog named Hime. It means Princess in Japanese. [/derail]
100! is not more than MILLIONS of digits..?!
100! = 93326215443944152681699238856266700490715968264381
62146859296389521759999322991560894146397615651828
62536979208272237582511852109168640000000000000000
00000000
lolQuote:
Originally Posted by Tom Sawyer
@NickThissen 100! <> 93326215443944152681699238856266700490715968264381
62146859296389521759999322991560894146397615651828
62536979208272237582511852109168640000000000000000
00000000
because there sum is 639 which is not the correct answer for the porblem
Actually the answer I got was 648
vb.net Code:
I expect that the loop perito used started from 1 instead of 0 and thus missed the first 9.
ok the answer is correct.
but i still want to creat my own HugeInteger class ...
where should i start to be able to create such a class?
I've just started coding the HugeInteger class for you this afternoon, but didn't have enough time (at work) to get it done. I'll work on it again tomorrow and see how much I can put together. The basic idea on this is to create an integer array of n elements where each element stores a digit. So if you have an array of the size 200, your huge integer max size can be 200 digit long. As for the calculation, you'll need to be able to perform the most 2 basic calculations: addition and subtraction. The othe calculations can be derived from these two later (for example, multiplication is just addition of the same number for n times, and factorial calculation is just multiplications in a special pattern). If you want to try on your own, that's the idea.Quote:
Originally Posted by perito
Here is something to get you started... I didn't throughoutly tested it though... Only did a few tests of adding, subtracting, multiplying, dividing, and factorial. For factorial, i tested 0!, 1!,...., 11!, 12!, 52! and 100! and they all came out alright. Didn't test for any factorial over 100! (no proof to compare the result to)
You need to download the attached HugeInteger class and add it to you project. To use it, you can simply do
Code:Create a new huge integer object initialized to zero
Dim hugeInt As New HugeInteger()
'or to create a huge integer object from string
Dim hugeInt As HugeInteger = HugeInteger.FromString("11118576452383404756482374")
'For calculation, these operators are overloaded: +, -, *, \, >, =, <, >= and <= so you can just use it as any other numeric type
Dim sum as hugeinteger = hugeint1 + hugeint2
Dim fact As HugeInteger = HugeInteger.Factorial(100)
'To display the value of a huge integer object, you need to call its ToString method
MessageBox.Show(myHugeInt.ToString)
I considered this project from a different angle, using binary math rather than a single digit per integer. I think I may have come up with a slightly faster solution....except that converting it into a string is such a chore I don't feel like doing it.
This seems like it might be an interesting coding contest contestant, as I feel there ought to be a faster solution, but from what I looked at, the problem would not so much be in creating a faster class for calculations, it would be in creating a class that was both faster in calculations, and that would be able to convert to a string easily. Without the string, a number of that size is of very limitted use, as you could never represent it. My class created a giant binary number of arbitrary length. If there is any way to convert that into a readable decimal value, I don't know it. Turning it into a readable Hex number wouldn't be all that difficult, but converting a massive hex number to a string might not be so easy.
It would be interesting to take a look inside the Java BigInteger class (I think that's what it's called) to see how they've implemented it. Can the Java class library be disassembled like the .NET class library? Anyone fell like doing it?
I think this is it.Quote:
Originally Posted by jmcilhinney
Edit: I've been extremely restless lately, I wouldnt mind (trying to) convert that to VB.Net code over the weekend.
You should be able to do that with one hand while reciting Shakespeare and playing Beethoven's 5th with the other hand. ;)Quote:
Originally Posted by Atheist
My thought exactly:DQuote:
Originally Posted by jmcilhinney
...after looking more at the code...I suspect I'll fail.
@stanav, I don't use VB.Net but I wonder, with your HugeInteger class:
How long does it take to calculate Factorial(1000) and Factorial(10000)?
Is that practical to use your class in these cases?
Here is the answer for Factorial 100, calculated in 100ms.
1101100110000100101100100111011000011100101011101110000100100000001101001010100101000110101010100101 1101111011010010000001101000101101110100101100110111011111001101001110000111010110010000110110101101 1001010010100001110100011001000011100110111110001000000111001000101110100010101010111000011001100101 0100101000010000011000110111011001011001110110111001011101101001011101110100010110000001011101010001 0011100110101110001100001101000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000
Now if I could only get it out of binary.
u dont have to do it alone...Quote:
Originally Posted by Atheist
The HugeInteger class supports huge numbers upto (2^32) digit long (that's the limit of the array used to store the digits), and it has a MaxLenght constant variable that you can set. For factorals, just to be on the safe side, the maxlength shuld be set to twice the factoral number... For example, if you're to calculate 1000!, you shoud set maxlength to 2000... And of course the larger maxlength is, themore resources (memory) it takes. So you don't want to set maxlength to 1000 while only calculate factorials upto 200!.... As for how fast it'll do 1000! or 10000!, it's a trivial quesion because the speed on each computer is different... For example, on a 8 year old computer it might take 30 seconds to do 10000! while on a newer PC it takes only fractions of a second. If you want to find out the answer for your self, just download the class and test it out... Plain and simple :)Quote:
Originally Posted by anhn
Factorial of 1000 takes 8530 bits.
Factorial of 2000 takes 19053 bits.
!100 =
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,599,993,2 29,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,0 00,000,000
I won't post !1000 (2568 digits in 2 seconds) or !5000 (16326 digits in 12 seconds)
I went from doing it in binary to decimal, and while I was at it I did +-*/, as well as factors. My guess is that I can do integer math on numbers 32K digits wide.(How do you test this stuff, and why did I OCD this :eek: )
Divide works but geeeeezzz, can you say slow?
how are u doing it? what code are u using?Quote:
Originally Posted by dbasnett
Arrays of integers as the digits. Then good ol' 1st grade techniques.
Factorial 10,000 is 35,660 digits long and takes about 60 seconds.
is the code private? can u post it here?Quote:
Originally Posted by dbasnett
See my Large Integer post today.
My Factorial function written in VBA (Office 2003), without using any API function, can calculate Factorial of 10000 in around 30 seconds on my desktop PC (Intel Core 2 CPU 6400 @ 2.13GHz, 2.00GB RAM).
I am hoping the speed can be improved.
The factorial of 10000 contains 35660 digits with 2499 trailing zeroes.
1000! : 0.094 seconds, Length = 2568, Trailing Zeroes: 249
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048 0047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950 5950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476 6328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791 4385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155 8611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151 0273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215 6683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535 3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200 0158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760 8850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403 1274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786 9061172601587835207515162842255402651704833042261439742869330616908979684825901254583271682264580665 2676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946 5955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657 2450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623 7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179 9702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819 3723886426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233 4482801505139969429015348307764456909907315243327828826986460278986432113908350621709500259738986355 4277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994 8717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636 7740459574178516082923013535808184009699637252423056085590370062427124341690900415369010593398383577 7939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000
That beats me. I am a Mobile Centrino, 1.8Ghz, 512MB.
Even you haven't seen this here is a link with some big factorials
http://www.rain.org/~mkummel/stumpers/28jan00b.txt
Improve speed? Use something faster than a scripted language. VB.Net should be better but C++ would be optimal.Quote:
Originally Posted by anhn
Sure, with lower level language that will be much faster. But my challenge is to use "native" VB 6.0 or VBA functions/components to write the factorial function, without any other external library.Quote:
Originally Posted by kasracer