Factorials - using primes - HELP

[dbasnett]

Could someone give me examples with explanations of how factorials are calcualted using primes.

I have found this:

10! = 2^8 * 3^4 * 5^2 * 7

which gives the correct answer. I see that the calculation uses all the primes less than the number(10), but where did the exponents come from?

What does 20! look like and why?

[anhn]

20! = 2^18 * 3^8 * 5^4 * 7^2 * 11 * 13 * 17 * 19

Should this be in CodeBank?

Function PrimeUpto(ByVal Num As Long, Count As Long) As Variant
   If Num < 2 Then
      Count = 0
   Else
      Dim j As Long
      j = 0
      ReDim p(0 To j) As Long
      p(j) = 2
      If Num > 2 Then
         Dim i As Long
         ReDim n(2 To Num) As Byte
         Do
            For i = 2 * p(j) To Num Step p(j)
               n(i) = 1
            Next
            For i = p(j) + 1 To Num
               If n(i) = 0 Then
                  j = j + 1
                  ReDim Preserve p(0 To j) As Long
                  p(j) = i
                  Exit For
               End If
            Next
         Loop Until i > Num
      End If
      Count = j + 1
      PrimeUpto = p
   End If
End Function

Sub FactorizeFactorial()
   Dim Num As Long
   Dim n As Long
   Dim m As Long
   Dim m1 As Long
   Dim i As Long
   Dim p As Variant
   
   Num = 20
   
   p = PrimeUpto(Num, n)
   ReDim expCount(0 To n - 1) As Long
   For m = 2 To Num
      m1 = m
      For i = 0 To n - 1
         Do While m1 Mod p(i) = 0
            expCount(i) = expCount(i) + 1
            m1 = m1 \ p(i)
         Loop
      Next
   Next
   For i = 0 To n - 1
      Debug.Print p(i), expCount(i)
   Next
End Sub

[dbasnett]

First of all thanks. I had to modify it enough to get it to run. Now can I understand it. BTW - I already had written a prime sieve, but it was interesting to see how you did it. Don't know if I like yours more than mine, or which is faster. I'll let you know.

Thanks, Thanks, Thanks!!!!

[anhn]

I wrote those Function and Sub at around 12:30AM last night after a long tired day. I know it's not good but it works. It uses the classic cross-off method that I used to teach year-12 students some 30 years ago.

There are some fast (but complicated) algorithms to generate prime numbers (prime sieve) but I have not much time to read. Do not expect my function PrimeUpto() is fast.

[Logophobic]

but where did the exponents come from?

Expand to prime factors:
10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 *3 * 2
= 2 * 5 * 3 * 3 * 2 * 2 * 2 * 7 * 2 * 3 * 5 * 2 * 2 * 3 * 2
= 2⁸ * 3⁴ * 5² * 7

[dbasnett]

Thanks to everyone that helped. I have totally re-written my factorials code using this method.

However, I did not see much, if any performance increase. Once again it comes down to mulitplying. I am so frustrated.

[jemidiah]

Unless you can efficiently factor the number [very tough] I'd be impressed if this gives any performance increase.

Could you precompute a table of useful factorials? If you had the factorials of each power of 10 (for instance) you'd be able to skip most of the multiplications each time.

[dbasnett]

I doubt that I am doing a good job at factoring the number. But I did get some performance increase after reading about exponents. Cut the number of multiplications in half. For example:

3^9 = 3((3^4)^2)

I also stopped pre-computing values. Example:
2^64 was being turned into
65536^1
65536^1
65536^1
65536^1

Still trying to figure out why that helped, though I think it has to do with the length of the numbers that end up being manipulated in multiply.

My goal is was to get decent performance. I was using 10000! as my benchmark number and anhn's performance statements (another thread). When I started it was taking 60 seconds on my 1.8Ghz laptop. I am now under 10 seconds, and still not happy, but what is my next step. Re-write number 4?

[anhn]

You have done a good job. Try harder as you are still far behind me.

Now I can manage to calculate 10000! in ~2.0 seconds on my desktop PC (Intel Core 2 CPU 6400 @ 2.13GHz, 2.00GB RAM). It still can be made faster.

I have written another routine to factorize numbers. If a number is a Long (<= 2^31-1) then the routine can give all its factors almost instantly.

Still trying to figure out why that helped, though I think it has to do with the length of the numbers that end up being manipulated in multiply.

I did tell you in a PM, use as large number as possible (haft-size of Decimal is the best) to reduce numbers of items you need to do multiply in form of "big integers".

[dbasnett]

Did you mean 100,000! in under 2 seconds? When I changed to decimals the performance got worse, so it must be something else, like how we multiply, but if I understood you correctly we are doing that the same.

[anhn]

Now I can manage to calculate 10000! in ~2.0 seconds

Please count number of zeroes carefully. Don't say it wrong.

Use Decimal size (up to 29 digits), I can reduce number of multiply items from 10,000 Long numbers to 2,487 Half-Decimal numbers, that is less than 25%, and perform "big multiply" on these 2,487 Decimal numbers (maximum of 15 digits). Of course, it will take some overhead time to join 10,000 small items to 2,487 large items but that is not much if you can do it efficiently.

Carefully choose the max-limit of these Half-Decimal numbers so that the result of multiply of 2 Half-Decimals will never exceed the upper limit of Decimal.

The time to multiply 2,487 Half-Decimal numbers (up to 29 digits, use Base-10^14) is longer than the time to multiply 2,487 Long numbers (up to 9 digits, use Base-10^4), but it is much less than the time to multiply 10,000 Long numbers. Even it is also faster than using Int64 (up to 20 digits, use Base-10^9) in VB.NET.

[dbasnett]

On my laptop PC (Intel Centrino M@ 1.8GHz, 2.00GB RAM) I am at 5 seconds for 10,000! using forms and 4.5 seconds as console.

anhn - are you resizing arrays as you go?

[anhn]

To compare the speeds, I suggest you do coding in Excel VBA.
I coded with Excel-2003 at work.
Have a try for 20,000!

My code uses 2 arrays without resize them,
ReDim each just once for just large enough to hold all digits,
they will be thrown away at the end after converting to String.

This is my output:

10000! = 2.84625968091705451890641321211986889014805140170279 _
         ...other 33060 digits... _
         02609169730998153853939031280878823902948001579008E+35659
         35660 Digits, 2499 Trailing Zeroes, 2.078 seconds.

20000! = 1.81920632023034513482764175686645876607160990147875 _
         ...other 72238 digits... _
         34247072560412074588342330639746430339183328362496E+77337
         77338 Digits, 4999 Trailing Zeroes, 9.109 seconds.

[dbasnett]

10,000! - 1 second
20,000! - 4.8 seconds

Stopped doing base 10 math, and voila.

[anhn]

That is fabulous! Congratulation!
That is twice faster than mine.
Did you work on VB.NET or VB6 or Excel VBA?
I am sure Excel VBA is much slower than the others.

[dbasnett]

VB 2008 Express. All times so far are in the IDE. I am < 1 second for 10,000! and about 80 seconds for 100,000!

[dbasnett]

That is fabulous! Congratulation!
That is twice faster than mine.
Did you work on VB.NET or VB6 or Excel VBA?
I am sure Excel VBA is much slower than the others.

I have to tell you that this 'trip' I have been on is in part due to you. I also can't tell you how helpful you have been, and how much I appreciate it. I looked back at my notes and realized how far I have come. Not only did I get faster at doing factorials, I also received a math refresher.

So Thanks!

BTW - 51 seconds for 100,000! is going to be good enough for now. Time to cleanup the mess I made of the rest of it, and then who knows...

100,000! is 456,574 characters in length and starts like this

2824229407960347874293421578024535518477494926091224850578918086542977950901063017872551771413831163 61071361173736196295147499618312391802272607340909383242200555696886678403803773794449612683

[anhn]

Now, you know the main trick on calculate large factorial.
I still have some small tricks on it that I haven't told you.
Have you seen in my results it says 10,000! has 2499 trailing zeros and 20,000! has 4999 trailing zeros? I am sure you will have some ideas from this.

I don't mind, but if you can share your code, probably I may have some more inputs so we can work together to build the best project on factorial.

If you can do 100,000! in 51 seconds, what you will do if your application requires to calculate 100,500! and 101,765!, it will take another 2 minutes or so to do that?

I love this stuff as I used to be a math teacher more than 30 years ago (no longer now). At that time, I cannot dream to calculate 5,000! (and what for?).
For a show off to students, I was able to remember by heart 20 decimal numbers of Pi, wrote it on the chalk board, gave year-12 students some series formulas and request them to use that to prove what I wrote on the board is correct. My smartest student took a week to do that by hand.

[dbasnett]

Let me get the code cleaned up and we will go from there.

[dbasnett]

OK, do you want me to send the project to you? How? It is VB2008 Express.

[anhn]

Can you just send me the code modules via PM.
It would be nice if you can convert it to VB and put it in Excel VBA. If not I will try to do it myself (I am not familiar with VB.NET syntax)
I don't have VB....Express nor VB6.

Thanks.

[dbasnett]

I tried to send via PM, but it is way to large, and you don't have an email, so? I also have to tell you that you will be better off downloading VB 2008 Express (it's free) and working on it there.

[anhn]

I got 2005 at home, but I have nothing at work.
How big? I think just the plain code after Zipping it cannot be more than 60KB.

[dbasnett]

Attachment 62673

Let me know when you get it

[anhn]

I got it. Thanks. There is only one vb file after unzip that is only 22KB.
I will look at it when I have time.
We are in different time-zones. When I am writting this I just come to my Office (9:00AM now).

[dbasnett]

Great, I look forward to hearing from you. On the forum today we tried to figure out if 0002 was a number or not.

[anhn]

On the forum today we tried to figure out if 0002 was a number or not.

What do you mean?

[dbasnett]

Read them all the way through.


http://www.vbforums.com/showthread.php?t=512075

http://www.vbforums.com/showthread.php?t=512130

[anhn]

@dbasnett, have you check your PM? I sent you 2 of them.

[Jánošík]

I am trying to split big numbers (up to 10^20) in to their prime factors.
I must say I am realy impressed after reading these postings...

I have tried a few algorithms already, but either they can't generate big enough prime factoers, or they are much to slow! Can somebody point me the right direction how to do this?

PS: I am using VB6

[jemidiah]

This thread has very little to do with factoring numbers. You should start a new thread on that topic. Your problem is certainly possible, though--for instance, I just used the Python library sympy's factorint function to factor 100 randomly chosen integers between 10^19 and 10^20 in under 10 seconds. I'd be surprised if a similar VB6 library didn't already exist.