Well, to help you, here's a factorial function using a dynamic programming approach. It can also be done recursively but it's a little less efficient, not that efficiency is very important when you're using VB.
VB Code:
Function Fact(x As Double) As Double
Dim i As Double
i = 1
For i = 1 To x
i = i * x
Next x
Fact = i
End Function
It uses Double datatypes for input and output because a standard 32-bit integer will only be large enough for values of around 12!. Doubles allow you to represent much larger values but only to a limited precision of around 15 significant figures.
You can use that function to calculate your mCn value with a function like this:
VB Code:
Function mCn(m As Double, n as Double) As Double
mCn = Fact(m) / ( Fact (m - n) * Fact(n) )
End Function
That uses Doubles again but you will probably want to convert that back to an integer value if the range of your data will allow it. Some precision will be lost using Doubles, so you probably won't get an exact integer back, just one that's very close.
To calculate N! / (N - R)! * R!, do not calculate 3 factorial values. Note the following.
Number of possible poker hands with 52-card deck is the following.
52! / 47! * 5! = 52*51*50*49*48 / 5*4*3*2*1
The above is easier than calculating the three factorials. Using Doubles, you will probably get a correct integer result for the above, no matter how you do it.
For other combination problems, it might be better to do something like the following.
(52/5)*(51/4)*(50/3)*(49/2)*(48/1).
If you round to an integer, you are likely to get the correct integer result for many nCm calculations. If you get tricky, you can get correct integer results for many of these problems, using just a little extra code and a little extra time.
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
Anyway Harry's loop looks a bit odd to me. I've changed it a bit.
VB Code:
Function Fact(byval x As Long) As Double
Dim i As Double, j as Long
i=1
For j = 2 To x 'you don't need to start at 1, theres no point really
i = i * x
Next j
Fact = i
End Function
I've not tested it but it looks about right to me.
Plus I changed x to long (and added j as another long), factorials get bloody large very quickly and would easily cause an overflow way before we get into double territory! We may not even need to use longs, integer might be adequate for x and j.
Robbert: Could you explain about not being able to assign a decimal value to a Long, but assigning to a Double is Okay. As far as I know the following code would display the same values in the Text Boxes.
VB Code:
Dim X As Long
Dim Y As Double
X = 53698
Y = 53698
TboxA.Text = Cstr(X)
TboxB.Text = Cstr(Y)
Internally, the values are binary rather than decimal, requiring conversion of decimal input to binary and later conversion back to decimal for output. In some instances, the conversions will result in the display of non integers (or extremely large integers) different from the input data.
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
Thank you everyone for the replies, in the follwoing site link there were two functions to calculate the Factorial of a number. But they give an overflow error if the number is > 12. I am required to compute the factorial of numbers upto 99.
Is there any other way to tackle this problem.....,
How about using a variant datatype ?????
VB Code:
Function FactorialTheBoringWay(intNumber As Long) As Long
Dim i As Integer
Dim lngResult As Long
lngResult = 1
For i = 2 To intNumber
lngResult = lngResult * i
Next i
Factorial = lngResult
End Function
Function FactorialRecursively(intNumber As Long) As Long
In fact to calculate mCn you won't need factorials, most important you are limited to the hardware meaning CPU power.
Guv Posted two approaches the first which is simplification of the the expression with factorials and the second which can handle larger values on n*m but is limited to floating point calculation.
52! / 47! * 5! = 52*51*50*49*48 / 5*4*3*2*1
(52/5)*(51/4)*(50/3)*(49/2)*(48/1).
something like:
Code:
X=1
for M=M-N to M
X*=C/N //or X*=C and Y*=N and finally X/=Y for the first alternative
M--
next
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Originally posted by Guv Robbert: Could you explain about not being able to assign a decimal value to a Long, but assigning to a Double is Okay. As far as I know the following code would display the same values in the Text Boxes.
VB Code:
Dim X As Long
Dim Y As Double
X = 53698
Y = 53698
TboxA.Text = Cstr(X)
TboxB.Text = Cstr(Y)
Internally, the values are binary rather than decimal, requiring conversion of decimal input to binary and later conversion back to decimal for output. In some instances, the conversions will result in the display of non integers (or extremely large integers) different from the input data.
This works fine if the values are hole numbers, but try the same code with these numbers :
x= 53698.23412334456
y= 53698.23412334456
The long value will only show the hole number, the double value will show everything.
Ashky, as I said previously, 32-bit integers overflow past 12!. This is because they have one 32-bit pattern for every single integer in the range -2,147,483,648 to +-2,147,483,647. They use a 2's complement binary representation, which is easily found on the net if you're intereted in the details.
Doubles, on the other hand, are a little different. Doubles are 64-bit which gives them a much larger number of discrete values to begin with. They also represent numbers differently to integer variables. The data is stored in something a lot like standard form, but using a binary numbering system rather than decimal.
What this means is that Doubles have a much greater range of values that they can represent, but with the drawback that they can lack precision. You may want to store the number 1234567890123456.1234567890 but in all likelihood this number will get rounded after it has been converted to binary, and will come out as a (slightly) different number when converted back into decimal.
So, in short, doubles let you use much larger numbers than integers but lack some precision. If you want to store really huge numbers accurately, you really need to implement a new datatype that can fulfil your needs. Commonly people do this with string representations of numbers, and write their own functions to handle operations on these string-numbers, like addition and multiplication. There are probably a lot of these kinds of datatypes already written that you can just borrow and use in your app.
Other than that you could use a language with a more scientific or mathematical bias that already handles this. Python, for instance, handles arbitrarily long numbers of any type (including complex numbers).
wossname: You're right, my code was a bit messed up, oops. I didn't check it properly.
Guv: I see that all these calculations aren't necessary, but how would you do it your way? Do you simplify the expression at run-time or does the expression reduce to something much simpler already? Either way, it's a neat approach.
Originally posted by HarryW wossname: You're right, my code was a bit messed up, oops. I didn't check it properly.
You were drunk right? Thats what my code looks like when I'm pissed too!
I am curently developing a modified version of the BASIC syntax in a VB add-in, I'm calling it "VB for Alcoholics". It lets you gibber away to your hearts content, ignoring every single command you issue, replacing it with normal, sober and intelligent nothingness.
You start and finish with an empty project, safe in the knowledge that in your drunken stupor, you haven't accidentally erased the server's tape drive or bitblitted a rude picture of the bosses wife to every monitor in the office.
ThinkTank2: My HP calculator gave 9.332 621 544 39 E155, which agrees with the first 12 digits of your result. I did not count digits in your result, but assume it is correct. How did you obtain it?
Ashky: If you use a Double instead of a Long, your code looks as though it should work.
I do not understand the Kedaman code, but it is likely to work. He seldom makes mistakes in code or math, but often uses esoteric methods which confuse me. Something like the following should work for mCn (I did not test it, so caveat emptor).
VB Code:
Function mCn(m as Integer, n As Integer) As Double
Dim Result As Double
Dim J As Integer
If n > m Then
MsgBox(“n must not be greater than m”)
mCn = 0
Exit Function
End If
Result = m
For J = 2 to n
Result = Result * (m - J + 1) / J
Next J
mCn = Result
End Function
Others: I do not understand the insistence on a Variant being the only way to go in VB. A Double will surely allow calculation of factorials a little beyond 175!. I personally avoid Variants. I generally know what my data looks like and choose the Data Type accordingly. There might be some reason for using a Variant to hold large decimal values, but I seldom need anything that cannot be stored in a Double.
VB cannot hold more than 12! In a Long variable. A VB Double provides about 15 decimal digits of precision, which would allow an exact value of 17! (I think), but not much more.
While a VB Double will not provide an exact value of 99! (Over 155 decimal digits), you can surely calculate an approximate value. My HP calculator will calculate factorials a little beyond 250! (About 490 decimal digits), with about 12 digit precision. The calculator floating point (like a VB Double) allows a larger exponent (up to 500) and less precision (about 12 decimal digits) than VB (308 & 15, respectively).
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
: I do not understand the insistence on a Variant being the only way to go in VB. A Double will surely allow calculation of factorials a little beyond 175!. I personally avoid Variants. I generally know what my data looks like and choose the Data Type accordingly. There might be some reason for using a Variant to hold large decimal values, but I seldom need anything that cannot be stored in a Double.
Variant datatype is an abstraction layer for all integrated types, classes and UDT's arrays of objects or integrated types but not arrays of UDT's for some freaky reason, and a set of types that cannot be created such as null, empty and error, and also Decimal, which is 96 bit integer(about 28 decimals) (achieved by casting a variant to CDEC() and then assigning a STRING to it) and also the largest integrated integer datatype in VB. Double's are 64 bit floating points and might often be best in physical, practical issues while mathematical or logical issues require exactness that floating points don't provide.
I'm sorry about my code, haven't used VB for quite a while and i soon forget that there's no other assignment operators than =
Code:
Function mCn(m as Integer, n As Integer) As Double
dim X as double,Y as double
X=1
Y=1
for M=M-N to M
X=X*C/N
M=M-1
next
mCn=X
End Function
Code:
Function mCn(m as Integer, n As Integer) As Double
dim X as integer, Y as integer
X=1
Y=1
for M=M-N to M
X=X*C
Y=Y*N
M=M-1
next
X=X/Y
mCn=X
End Function
And I do make mistakes, especially when I code without a compiler
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Originally posted by Guv ..... There might be some reason for using a Variant to hold large decimal values, but I seldom need anything that cannot be stored in a Double........ A VB Double provides about 15 decimal digits of precision, which would allow an exact value of 17! (I think), but not much more.......and less precision (about 12 decimal digits)
I'm a little puzzled over the Emphasis on Decimal Precision when it comes to calculating Factorials {n!}. Surely when one calculates n!, you'll never return a decimal?
{Hmmm, lets see, 5!, 5*4*3*2*1, nope, no decimal in sight! }
Originally posted by Guv ThinkTank2: My HP calculator gave 9.332 621 544 39 E155, which agrees with the first 12 digits of your result. I did not count digits in your result, but assume it is correct. How did you obtain it?
Mathematica !!!!
Others: I do not understand the insistence on a Variant being the only way to go in VB. A Double will surely allow calculation of factorials a little beyond 175!. I personally avoid Variants........
.....A VB Double provides about 15 decimal digits of precision, which would allow an exact value of 17! (I think), but not much more.
You might want to try using logs instead of reals, integers, etc:
Code:
Function Factorial_as_Log(X As Integer) As Double
'
' Non-recursive factorial, returning f as f=f+log(f)
'
Dim i As Integer, f As Double
f = 0#
For i = 2 To X
f = f + Log(i)
Next i
Factorial_as_Log = f
End Function
Thinktank2: I envy your having Mathematica. I use MathCad 7, which is excellent, but not as good as Mathematica.
I said the following.
A VB Double will surely allow calculation of factorials a little beyond 175! . . . . A VB Double provides about 15 decimal digits of precision, which would allow an exact value for 17! (I think), but not much more . . .
There is not really a discrepancy in the above, although I have discovered that overflow occurs with 175! (170! Is about the limit for a VB Double). 17! is approximately 3.55687E14, which is a 15 digit integer in decimal notation, allowing a VB Double to hold its precise value. 170! Is approximately 7.25742E306, which is a 307 digit integer. VB can compute an approximate value for 170!, but if converted to a 307 digit decimal value, only the first 15 digits would be correct.
Note that 52! Is approximately 8.06582E67, which is a 68 digit decimal integer. While VB could not compute an exact integer value for 52!, a VB program could compute accurate probabilities relating to a standard 52-Card deck, even though such calculations might involve computation of 52!
All: It seems that I have been using mathematical jargon rather than being college professor precise. I am sorry: I did not think this context required formal definitions.
When specifying the precision of a value, the term decimal digits refers to the most significant digits of the value, not necessarily to the first six digits to the right of the radix point. In most contexts, decimal is assumed and omitted. In a computer context, one might specify the precision as a number of decimal, octal or hexidecimal digits, so decimal in decimal digits of precision refers to the radix, not the digits to the right of the radix point. One might refer to the velocity of light as 186,282 miles per second, and say that this value provides 6 decimal digits of precision, while the value 299,792.458 kilometers per second provides at least 8 decimal digits of precision (I am not sure about the 9th digit)
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
there should be a zero for each number ending with 5 or 0:2000/5=400
There should be a zero for each number ending with 50 or 00: 2000/50=40
There should be a zero for each number ending with 500 or 000: 2000/500=4
now where are the missing 55?
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Kedaman: Perhaps there are two zeros for each number ending in 50 or 00, and three zeros for each ending in 500 or 000. You might have to make adjustments for double & triple counts. Numbers ending in a single zero include those ending in 50, 500, double zero, or triple zero. Similarly numbers ending in double zero include those ending in 500 or triple zero.
NotLKH: Perhaps Thinktank2 can use mathematica to verify for you.
Using my above comment about the Kedaman post might give you a clue to verifying the trailing zeros.
Perhaps you can use VB to compute the largest factorial it is capable of computing (170!, approximately 7.25742E306). Then compute a lot of products like 171*172*173 . . . If you divide each product by something like 1.00E200, and multiply all these products, you can verify the first 15 digits or so of your alleged value.
Similarly, you could use your own software to calculate 1950!, then use VB to calculate 1951*1952*1953 . . . *1999*2000. Using these two values you could verify the first 15 digits of 2000! via VB calculations. If you do half a dozen similar verifications of the first 15 digits of other large factorial values, you should be able to either discredit or become confident in your software. You can also use the kedaman idea to verify the number of trailing zeros for various values.
If you use your software to calculate several factorials of large but almost equal numbers (say 1495!, 1500!, & 1505!) you can use VB or a hand calculator to verify self consistency of the the total number of digits, the first 15 or so digits, and the number of trailing zeros.
All: Does anybody (including NotLKH & Kedaman) really care about the exact value of 2000! ?
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
Originally posted by thinktank2 I did a String Comparison using the StrComp function and it says they are the same.
Anyway here is the mathematica output.
Thanks for the verification. they Are Identical. I was pretty sure it worked, since it agreed with the posting of 99!. So, it seems that My program can return n! of up to 32k in length.
Guv, yes I assumed that those numbers that ended with 00 and 50 were counted twice, 000 and 500 three times. Now when I think about whatyou said about 25's and 75 I think I know where those 48 of the 55 0e's are hiding.
25*4=100, 75*8=600.. one extra beside ending with 5
125*8 got one extra besides the above and ending with 5
375*16 and so on...
there should be 40 of the first and 8 of the latter
Oh well, only 7 more to go
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
By my calculations 2000! yields a number many times larger than the number of elementary particles in the known universe!!!
I sh*t ye not.
In fact it is many orders of decimal magnitude larger. I would sincerely like to know what use numbers this large could be put to. Encryption doesn't count simply because there is no chance that any current algorithm can crack 160 bit encrytion, even running on ASCI Red or any other SC.
Originally posted by kedaman Guv, yes I assumed that those numbers that ended with 00 and 50 were counted twice, 000 and 500 three times. Now when I think about whatyou said about 25's and 75 I think I know where those 48 of the 55 0e's are hiding.
25*4=100, 75*8=600.. one extra beside ending with 5
125*8 got one extra besides the above and ending with 5
375*16 and so on...
there should be 40 of the first and 8 of the latter
Oh well, only 7 more to go
This "Account for the 500 Zero's" Investigation is intriguing!
I decided to try it this way.
For the product of 2000 thru 1, for every 5 and 2 combination, you get 1 zero. So, if you count the number of times 5 is a factor of n, and similarly 2 is a factor of n, keeping a running total of both 2 counts and 5 counts, as n goes from 1 to 2000, then the number of zeros should be the smaller of the two running counts.
for example, from 21 to 30, it breaks down this way:
VB Code:
n: Num2's : Num5's
21 0 0
22 1 0
23 0 0
24 3 0
25 0 2
26 1 0
27 0 0
28 2 0
29 0 0
30 1 1
So there are 8 twos, and only 3 fives, so with my theory, mult(21 thru 30) should end with 3 zero's.
And, since 21*...*30 = 109027350432000, we see that indeed it Does end with 3 zero's.
So, with such a limited test, it seems my theory is sound.
it returns 1994 twos, and 499 fives, so since 499 is the smallest, there should be 499 zeros at the end of 2000!.
So, wheres my missing 0? Whats wrong with this Checker Progie? Where is it missing a 5, and more than likely a 2 also, since both are calculated similarly?
[EDITED]: Ahhh, Good! After double checking 2000!, There is only 499 zero's at the end of 2000!, NOT 500.
Last edited by NotLKH; Jan 26th, 2002 at 01:58 PM.
NotLKH, Yes it makes sense:
There is a zero for each factor 5 since there's always a larger amount of 2's to to make a zero. So in other words
Zeroes=sumof( 2000\5^N )
where \ stands for integer division, the sum of N=1 to log(2000)/log(5) (integers above won't contribute to the sum.
The anwer is 499.
for n=1 to log(9000)/log(5):s=s+9000\5^n:next:?s
gives 2747 which makes me question your verification of 2248 trailing zeroes, count them again
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
it makes 2748, i forgot to null the variables, it was done in the immediate window, and the variables used seemed to be stored in IDE.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Took mathematica 4 minutes 32 seconds on a Celeron 600 MHZ with an Intranet web server, SQL server running in the Background + couple of other apps.
I should say mathematica was a pretty decent app.
It never got unstable, the maximum processor usage was something like 65% at one time. Copying the output to a text file was fun. Notepad or Word can't get that from Clipboard. So used the old dos edit. It took it some 6 minutes to paste.
It works for values less than 500, but Above 500, I'm not too sure.
-Thanks
-Lou
Yes both are correct !
Calculating the nCm (or Binomial coefficient as mathematica calls it) is faster than calculating Factorials. It did 987654 C 87 in less than a second !!!
Originally posted by NotLKH
[B]
which you later amended to 2748.
Thinktank2's code:
doh! I meant to post 2248 try it Basically It's the same thing as Thinkthank got, so there's no reason why it should produce a different result.
BTW, in your line :for n=1 to log(9000)/log(5)
Every time it loops, isn't it recalculateing the value of log(9000)/log(5)?
No, for unlike while or for in other languages evaluates the criteria once and then loops until the iterator is equal to it.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Factorial / Combination ??????????
Reply With Quote
}
