none
500 factorial algorithm ! RRS feed

  • Question

  • can you write an algorithm which can calculate 500 factorial.  ** scientific symbol(mode) is unauthorized**   Answer should be in String mode.
    Saturday, August 25, 2007 8:31 AM

Answers

  • Hi,

    Using code by user John Wein as mentioned in my previous post in this thread.

    This code will give you the answer.

    Just add one button to a FORM for this code to work.>>

    Option Strict On 
     
    Public Class Form1  
     
        Private Sub Button1_Click(ByVal sender As System.ObjectByVal e As System.EventArgs) Handles Button1.Click  
     
            MessageBox.Show(Factorial("500"))  
     
        End Sub 
     
        Private Function Factorial(ByVal ofThisStringsValue As StringAs String 
     
            Dim answer As String = "1" 
            Dim loopEnd As Decimal 
            Decimal.TryParse(ofThisStringsValue, loopEnd)  
            loopEnd = Int(loopEnd)  
            If loopEnd = 0 Then Return "You tried zero or some other text!!" 
            If loopEnd = 1 Then Return "1" 
            Dim start As Decimal = 2  
     
            Do 
                answer = Multiply(answer, start.ToString)  
                start += 1  
            Loop Until start > loopEnd  
              
            Return answer  
        End Function 
     
        Public Function Multiply(ByVal S1 As StringByVal S2 As StringAs String 
     
            Dim A(65535) As Byte 
            Dim B(65535) As Byte 
            Dim C(65535) As Byte 
            Dim I, J, K, IJ, L1, L2 As Int32  
            L1 = S1.Length - 1  
            For I = 0 To L1  
                A(I) = CType(S1.Substring(L1 - I, 1), Byte)  
            Next 
            L2 = S2.Length - 1  
            For J = 0 To L2  
                B(J) = CType(S2.Substring(L2 - J, 1), Byte)  
            Next 
            For I = 0 To L1  
                For J = 0 To L2  
                    IJ = I + J  
                    C(IJ) += A(I) * B(J)  
                    K = 0  
                    While C(IJ + K) > 9  
                        C(IJ + 1) += CByte(Fix(C(IJ) / 10))  
                        C(IJ) = CByte(C(IJ) Mod 10)  
                        K += 1  
                    End While 
                Next 
            Next 
            Dim S As String = "" 
            L1 += L2 + 2  
            For I = L1 To 0 Step -1  
                S += C(I).ToString  
            Next 
            'Remove any character "0" 's from the start of the string        
            'until a non-zero numeric character is reached.        
            Dim testChr As String = "" 
            Do 
                testChr = S.Substring(0, 1)  
                If testChr = "0" Then 
                    S = S.Remove(0, 1)  
                Else 
                    Exit Do 
                End If 
            Loop 
            Return S  
        End Function 
     
    End Class 
     
     

     

    Regards,

    John

    Wednesday, August 29, 2007 9:59 AM

All replies

  • Hi,

     

    Unfortunately there is no numeric data type that can handle the size of result for 500!. Tried it out using stirlings approximation using double data types and it results in infinity.

     

    Saturday, August 25, 2007 12:39 PM
  • hi, i knew it and i could write the algorithm of this question before, but i'm seeking for another way to solve. if you know the algorithm write it down !
    Sunday, August 26, 2007 9:04 AM
  •  schahinap wrote:
    hi, i knew it and i could write the algorithm of this question before, but i'm seeking for another way to solve. if you know the algorithm write it down !

    Hi,

    You would have to do what this function does but do the multiplication in a STRING.

    The factorial of 20 is 2432902008176640000 which I have verified by Windows Calculator in scientific mode.

    If you take

    the highlighted line

    out you get an overflow.

    You could then remove

    the highlighted line

    in the FUNCTION.


    Regards,


    John


    Private Function Factorial(ByVal ofThisValue As Integer) As String
    Dim answer As Long = 1
    Dim loopEnd As Integer = ofThisValue
    If loopEnd > 20 Then Return "Overflow!"
    Dim start As Long = 2
    Do
    answer = answer * start
    start = start + 1
    Loop Until start > loopEnd
    Return answer.ToString
    End Function

    Sunday, August 26, 2007 9:12 AM
  • Hi, S_DS, your code is not the answer of my the question. it doesnt work!! you can test your suggested way for 500 factorial, then you'll find, the answer of the question is not as easy as you thought.
    by the way, thanks for your guidance.

    Sunday, August 26, 2007 11:12 AM
  •  schahinap wrote:
    Hi, S_DS, your code is not the answer of my the question. it doesnt work!! you can test your suggested way for 500 factorial, then you'll find, the answer of the question is not as easy as you thought.
    by the way, thanks for your guidance.

    Hi,

    I know it is not the answer.
    Did you not read the 1st sentence of my 1st post in this thread?

    The method of calculation is though.
    If I arrive at a method to solve it then I will post my code.
    I know what 500 ! is approximately equal to anyway, which is a string 1135 numeric characters long!!

    1.2201 E 1134


    Regards,

    John

    Monday, August 27, 2007 8:26 AM
  • Hi John, please read my question exactly. i dont want the answer in scientific mode(symbole). i want to write an algorithm whcih can calculate this amount (500!) and give us the exact number, e.g in scientific mode we have 1.2201 E 1134. I want to write an algorithm which can caculate this amount and give back us a number with the len of 1135.
    *It was on of my olympiad question, i could solve it with using the matrixes and arrays, i'm seeking for another way to find the answer not the answer of 500! in scientific mode!!!!*
    bythe way, tnx.
    Monday, August 27, 2007 1:43 PM
  • Hi S_DS thanks for your guidance, i think you know what i want exactly. anyway i dont want the answer in scientific mode(symbole). i want to write an algorithm whcih can calculate this amount (500!) and give us the exact number, e.g in scientific mode we have 1.2201 E 1134. I want to write an algorithm which can caculate this amount and give back us a number with the len of 1135.
    **It was on of my olympiad question, i could solve it with using the matrixes and arrays, i'm seeking for another way to find the answer not the answer of 500! in scientific mode!!!!**
    Monday, August 27, 2007 1:53 PM
  • 500! is no different than any other factorial.  Just use a big number multiplier.  My previous post was the first Google search result.  I assumed that somewhere on that site there would be an algorithm that gave all the digits.

    Tuesday, August 28, 2007 9:27 PM
  • Hi schahinap,

    Thanks to the forum users John Wein and Digboy2000 for posting code in this thread.>>>>

    http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2063157&SiteID=1

    I will add to this post and show you a large number factorial in action.


    Regards,

    John

    Wednesday, August 29, 2007 8:32 AM
  • Hi,

    Using code by user John Wein as mentioned in my previous post in this thread.

    This code will give you the answer.

    Just add one button to a FORM for this code to work.>>

    Option Strict On 
     
    Public Class Form1  
     
        Private Sub Button1_Click(ByVal sender As System.ObjectByVal e As System.EventArgs) Handles Button1.Click  
     
            MessageBox.Show(Factorial("500"))  
     
        End Sub 
     
        Private Function Factorial(ByVal ofThisStringsValue As StringAs String 
     
            Dim answer As String = "1" 
            Dim loopEnd As Decimal 
            Decimal.TryParse(ofThisStringsValue, loopEnd)  
            loopEnd = Int(loopEnd)  
            If loopEnd = 0 Then Return "You tried zero or some other text!!" 
            If loopEnd = 1 Then Return "1" 
            Dim start As Decimal = 2  
     
            Do 
                answer = Multiply(answer, start.ToString)  
                start += 1  
            Loop Until start > loopEnd  
              
            Return answer  
        End Function 
     
        Public Function Multiply(ByVal S1 As StringByVal S2 As StringAs String 
     
            Dim A(65535) As Byte 
            Dim B(65535) As Byte 
            Dim C(65535) As Byte 
            Dim I, J, K, IJ, L1, L2 As Int32  
            L1 = S1.Length - 1  
            For I = 0 To L1  
                A(I) = CType(S1.Substring(L1 - I, 1), Byte)  
            Next 
            L2 = S2.Length - 1  
            For J = 0 To L2  
                B(J) = CType(S2.Substring(L2 - J, 1), Byte)  
            Next 
            For I = 0 To L1  
                For J = 0 To L2  
                    IJ = I + J  
                    C(IJ) += A(I) * B(J)  
                    K = 0  
                    While C(IJ + K) > 9  
                        C(IJ + 1) += CByte(Fix(C(IJ) / 10))  
                        C(IJ) = CByte(C(IJ) Mod 10)  
                        K += 1  
                    End While 
                Next 
            Next 
            Dim S As String = "" 
            L1 += L2 + 2  
            For I = L1 To 0 Step -1  
                S += C(I).ToString  
            Next 
            'Remove any character "0" 's from the start of the string        
            'until a non-zero numeric character is reached.        
            Dim testChr As String = "" 
            Do 
                testChr = S.Substring(0, 1)  
                If testChr = "0" Then 
                    S = S.Remove(0, 1)  
                Else 
                    Exit Do 
                End If 
            Loop 
            Return S  
        End Function 
     
    End Class 
     
     

     

    Regards,

    John

    Wednesday, August 29, 2007 9:59 AM
  • 122013682599111006870123878542304692625357434280319284219241358838584537315388
    1997605496447502203281863013616477148203584163378722078
    177200480785205159329285477907571939330603772960859086270429174547882424912726
    344305670173270769461062802310452644218878789465754777149863494367781037644274
    033827365397471386477878495438489595537537990423241061271326984327745715546309
    977202781014561081188373709531016356324432987029563896628911658974769572087926
    928871281780070265174507768410719624390394322536422605234945850129918571501248
    706961568141625359056693423813008856249246891564126775654481886506593847951775
    360894005745238940335798476363944905313062323749066445048824665075946735862074
    637925184200459369692981022263971952597190945217823331756934581508552332820762
    820023402626907898342451712006207714640979456116127629145951237229913340169552
    363850942885592018727433795173014586357570828355780158735432768888680120399882
    384702151467605445407663535984174430480128938313896881639487469658817504506926
    365338175055478128640000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000
    Saturday, May 2, 2009 2:42 PM
  • Hi BlackSack,

    Why did you want to post the actual result of the above code?

    If you wanted to you could simply add one Button and one large RichTextBox
     to a FORM and show the result in that instead like this.>>

    Option Strict On
    
    Public Class Form1
    
        Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    
            RichTextBox1.Text = Factorial("500")
    
        End Sub
    
        Private Function Factorial(ByVal ofThisStringsValue As String) As String
    
            Dim answer As String = "1"
            Dim loopEnd As Decimal
            Decimal.TryParse(ofThisStringsValue, loopEnd)
            loopEnd = Int(loopEnd)
            If loopEnd = 0 Then Return "You tried zero or some other text!!"
            If loopEnd = 1 Then Return "1"
            Dim start As Decimal = 2
    
            Do
                answer = Multiply(answer, start.ToString)
                start += 1
            Loop Until start > loopEnd
            Return answer.ToString
            Return answer
        End Function
    
        Public Function Multiply(ByVal S1 As String, ByVal S2 As String) As String
    
            Dim A(65535) As Byte
            Dim B(65535) As Byte
            Dim C(65535) As Byte
            Dim I, J, K, IJ, L1, L2 As Int32
            L1 = S1.Length - 1
            For I = 0 To L1
                A(I) = CType(S1.Substring(L1 - I, 1), Byte)
            Next
            L2 = S2.Length - 1
            For J = 0 To L2
                B(J) = CType(S2.Substring(L2 - J, 1), Byte)
            Next
            For I = 0 To L1
                For J = 0 To L2
                    IJ = I + J
                    C(IJ) += A(I) * B(J)
                    K = 0
                    While C(IJ + K) > 9
                        C(IJ + 1) += CByte(Fix(C(IJ) / 10))
                        C(IJ) = CByte(C(IJ) Mod 10)
                        K += 1
                    End While
                Next
            Next
            Dim S As String = ""
            L1 += L2 + 2
            For I = L1 To 0 Step -1
                S += C(I).ToString
            Next
            'Remove any character "0" 's from the start of the string         
            'until a non-zero numeric character is reached.         
            Dim testChr As String = ""
            Do
                testChr = S.Substring(0, 1)
                If testChr = "0" Then
                    S = S.Remove(0, 1)
                Else
                    Exit Do
                End If
            Loop
            Return S
        End Function
    
    End Class
    



    Regards,

    John
    Saturday, May 2, 2009 5:01 PM
  • Hi ALL,

    I've bumped this up to near this related thread.>>

    http://social.msdn.microsoft.com/Forums/en-US/vbgeneral/thread/4ec2bc19-b35d-4e27-9790-2bdf4b5ff153

    I may try the above with System.Numerics.BigInteger in Framework 4.0 for a speed comparison too.    ;-)


    Regards, John : Trying hard for another goal into the .Net!!
    Wednesday, June 23, 2010 5:33 PM
  • Hi ALL,

    I finally decided to revisit Factorial calculations after a long absence for a number of personal reasons.

     

    This code is for 2010 versions of VB.Net.

    ( I mentioned I would try this in my previous post in this thread but that was way back on June 23rd, 2010.  LOL!! )

    That is, it uses a feature of Framework 4.0

     

    1) Add one Button to your Form

    2) Add a reference to System.Numerics under the .Net tab when you select ADD REFERENCE under the PROJECT menu.

     

    Here is the code, notice the speed difference!!

    On my computer the BigInteger version takes 1 to 3 milliseconds at the most, while doing it the long way with a STRING takes around 1000 to 1300 milliseconds.

     

     

    Option Strict On
    Option Explicit On
    Option Infer Off
    
    Public Class Form1
    
        Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    
            Dim sw As New Stopwatch
            Dim result As System.Numerics.BigInteger = 0
    
            sw.Start()
            result = Factorial(500)
            sw.Stop()
            MessageBox.Show(result.ToString)
            MessageBox.Show("BigInteger calculation = " & sw.ElapsedMilliseconds.ToString & " milliseconds.")
    
            '-----------------------------------------------------------------------------
    
            Dim resultString As String
            sw.Reset()
            sw.Start()
            resultString = Factorial("500")
            sw.Stop()
            MessageBox.Show(resultString)
            MessageBox.Show("String based calculation = " & sw.ElapsedMilliseconds.ToString & " milliseconds.")
    
        End Sub
    
        Public Function Factorial(ByVal aBigInt As System.Numerics.BigInteger) As System.Numerics.BigInteger
    
            Dim result As System.Numerics.BigInteger = 2
            If aBigInt = 0 Or aBigInt = 1 Then result = 1
            If aBigInt > 2 Then
                For index As System.Numerics.BigInteger = 3 To aBigInt
                    result = System.Numerics.BigInteger.Multiply(result, index)
                Next
            End If
            If aBigInt < 0 Then
                Throw New Exception("Factorials are undefined for negative values.")
            End If
            Return result
    
        End Function
    
        Private Function Factorial(ByVal ofThisStringsValue As String) As String
    
            Dim answer As String = "1"
            Dim loopEnd As Decimal
            If Decimal.TryParse(ofThisStringsValue, loopEnd) = True Then
                loopEnd = Int(loopEnd)
                If loopEnd = 0 Or loopEnd = 1 Then Return "1"
                Dim start As Decimal = 2
    
                Do
                    answer = Multiply(answer, start.ToString)
                    start += 1
                Loop Until start > loopEnd
            Else
                Return "You passed the STRING based factorial function an invalid value!!"
            End If
    
            Return answer
        End Function
    
        Public Function Multiply(ByVal S1 As String, ByVal S2 As String) As String
    
            Dim A(65535) As Byte
            Dim B(65535) As Byte
            Dim C(65535) As Byte
            Dim I, J, K, IJ, L1, L2 As Int32
            L1 = S1.Length - 1
            For I = 0 To L1
                A(I) = CType(S1.Substring(L1 - I, 1), Byte)
            Next
            L2 = S2.Length - 1
            For J = 0 To L2
                B(J) = CType(S2.Substring(L2 - J, 1), Byte)
            Next
            For I = 0 To L1
                For J = 0 To L2
                    IJ = I + J
                    C(IJ) += A(I) * B(J)
                    K = 0
                    While C(IJ + K) > 9
                        C(IJ + 1) += CByte(Fix(C(IJ) / 10))
                        C(IJ) = CByte(C(IJ) Mod 10)
                        K += 1
                    End While
                Next
            Next
            Dim S As String = ""
            L1 += L2 + 2
            For I = L1 To 0 Step -1
                S += C(I).ToString
            Next
            'Remove any character "0" 's from the start of the string        
            'until a non-zero numeric character is reached.        
            Dim testChr As String = ""
            Do
                testChr = S.Substring(0, 1)
                If testChr = "0" Then
                    S = S.Remove(0, 1)
                Else
                    Exit Do
                End If
            Loop
            Return S
        End Function
    
    End Class
    


     




    Regards,

    profile for John Anthony Oliver at Stack Overflow, Q&A for professional and enthusiast programmers

    Click this link to see the NEW way of how to insert a picture into a forum post.

    Installing VB6 on Windows 7

    App Hub for Windows Phone & XBOX 360 developers.

    • Edited by John Anthony Oliver Monday, January 9, 2012 1:11 AM I have updated the FACTORIAL function for STRINGs from my earlier post that was posted on Wednesday 29th August, 2007. I have left that particular post as it was so you can compare the code if you wish.
    Monday, January 9, 2012 12:59 AM
  • Hi ALL,

    As the code in my post marked as answer here uses a routine ( using code by JohnWein ) to multiply two strings together where the strings can be really long numbers, I decided to update the STRING Multiply routine and the result can be found here.>>

    http://social.msdn.microsoft.com/Forums/en-US/vbgeneral/thread/9e7781d1-5f2f-47f1-9209-b004900183b5

     




    Regards,

    profile for John Anthony Oliver at Stack Overflow, Q&A for professional and enthusiast programmers

    Click this link to see the NEW way of how to insert a picture into a forum post.

    Installing VB6 on Windows 7

    App Hub for Windows Phone & XBOX 360 developers.

    Thursday, January 12, 2012 7:01 AM
  • there

    1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

    Monday, January 30, 2012 5:12 AM
  • I do not think that there is any data source to find 500!. If you do, it might not be the easiest calculation to find out 1x 2 x 3 x4........ x 500). It is just to hard
    • Proposed as answer by Anonomous123 Sunday, October 25, 2015 9:50 PM
    Sunday, October 25, 2015 9:50 PM
  • I do not think that there is any data source to find 500!. If you do, it might not be the easiest calculation to find out 1x 2 x 3 x4........ x 500). It is just to hard

    Anonomous (geez, you can't even spell the word correctly?),

    This thread is more than eight years old. It makes no sense to reply to it (at all), but yes it surely can be done.

    It would take a while and thus should be done on another thread. The result would likely need to be a large integer which didn't exist when this question was asked, but yes it can be done.

    Lastly, proposing yourself as the answerer is poor form, rude, and frankly doltish. Of course you think your reply is correct or you wouldn't have posted it! ;-)


    "I never failed once... It just happened to be a 2000-step process." -- Thomas Edison

    Sunday, October 25, 2015 9:58 PM
  • With NET 4 or higher, it's trivial:

    'Form with a Button, a NumericUpDown and a multiline TextBox
    'TextBox should be LARGE
    Option Strict On
    Imports System.Numerics ' Needs .NET 4 or higher and a reference to System.Numerics
    Public Class Form1
        Function GetFact(Number As Integer) As String
            Dim Result As BigInteger = 1
            Dim Multiplier As BigInteger = 1
            For Loops = 1 To Number
                Multiplier = Loops
                Result = BigInteger.Multiply(Result, Multiplier)
            Next
            Return Result.ToString
        End Function
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            Dim SW As New Stopwatch
            Dim Answer As String = ""
            SW.Reset()
            SW.Start()
            Answer = GetFact(CInt(NumericUpDown1.Value))
            SW.Stop()
            Dim ET As Decimal = CDec(SW.ElapsedTicks / Stopwatch.Frequency)
            TextBox1.Text = "took " & ET.ToString & " seconds " & vbNewLine & vbNewLine & Answer
        End Sub
    End Class
    
    

    • Proposed as answer by Mr. Monkeyboy Monday, October 26, 2015 1:18 AM
    Monday, October 26, 2015 1:15 AM
  • With NET 4 or higher, it's trivial:

    'Form with a Button, a NumericUpDown and a multiline TextBox
    'TextBox should be LARGE
    Option Strict On
    Imports System.Numerics ' Needs .NET 4 or higher and a reference to System.Numerics
    Public Class Form1
        Function GetFact(Number As Integer) As String
            Dim Result As BigInteger = 1
            Dim Multiplier As BigInteger = 1
            For Loops = 1 To Number
                Multiplier = Loops
                Result = BigInteger.Multiply(Result, Multiplier)
            Next
            Return Result.ToString
        End Function
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            Dim SW As New Stopwatch
            Dim Answer As String = ""
            SW.Reset()
            SW.Start()
            Answer = GetFact(CInt(NumericUpDown1.Value))
            SW.Stop()
            Dim ET As Decimal = CDec(SW.ElapsedTicks / Stopwatch.Frequency)
            TextBox1.Text = "took " & ET.ToString & " seconds " & vbNewLine & vbNewLine & Answer
        End Sub
    End Class
    
    

    Finally a .Net 4 and above answer to this thread I can appreciate. Which I'd never have even know existed (this thread) if Anomoose hadn't stumbled upon it!


    La vida loca

    Monday, October 26, 2015 1:21 AM
  • Hi ALL,

    Just showing how old threads get revisted from time to time.

    This one started off in August 2007 and had a visit in October 2015.

    I guess it just goes to show there are many ways to produce a result.  :-)  :-D

    Regards,

    John


    Regards,

    profile for John Anthony Oliver at Stack Overflow, Q&A for professional and enthusiast programmers

    Click this link to see the NEW way of how to insert a picture into a forum post.

    Installing VB6 on Windows 7

    App Hub for Windows Phone & XBOX 360 developers.

    Friday, January 8, 2016 11:46 PM