dcsimg
Results 1 to 22 of 22

Thread: Working with BIG numbers or LOTS of decimal places

  1. #1

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Working with BIG numbers or LOTS of decimal places

    This code contains quite a few mathematical functions and is capable of handling very large numbers or numbers with lots of decimal places. the limit to how big a number they can handle is not 1.79769313486232E+308 which is the normal double limit, but 1.79769313486232E+308 DIGITS LONG!
    functions included are: add, subtract, divide, multiply, square root, mod and power.
    they work by using long division, long addition etc
    they cannot handle negative numbers and the power function ( y^x ) only supports x being a whole number up to the size of double precision, but y can have decimals and be very large like the rest.
    it also needs some work as i know they can be alot faster, any suggestions to make them faster will be greatly appreciated.
    here they are, this must be put in a module:
    UPDATES:
    indented
    improved code with si's suggestions
    attatched a sample project which uses this module to calculate pi (end of second post)
    improved again
    Code:
    'Long math functions by karl baker
    'you are free to use these in your own projects as long as credit is given
    
    Public Function divide(tnum1 As String, tnum2 As String, tplaces As String) As String
    
    Dim result As String
    Dim times As Long
    Dim val3 As String
    Dim loopcount As Long
    Dim last As Boolean
    Dim num1 As String
    Dim num2 As String
    Dim places As String
    places = tplaces
    num1 = tnum1
    num2 = tnum2
    last = False
    'start the loop
    
    Do
        'loopcount keeps track of how many dp we have calculated
        loopcount = loopcount + 1
        result = 0
        times = 0
        'see how many times num1 goes into num2
        Do Until morethan(result, num1)
            result = add(result, num2)
            times = times + 1
            
        Loop
        result = subtract(result, num2)
        times = times - 1
        'if num1 goes into num2 exactly then this is the last calculation we need to do
        If result = num1 Then last = True
        
        If loopcount <> places And last = False Then
            val3 = subtract(num1, result)
            'multiply num1 by 10 to use in the next loop round for calculating the next digit
            num1 = multiply(val3, 10)
        End If
        
        If loopcount = 1 And last = False Then
            divide = times & "."
        Else
            divide = divide & times
        End If
    DoEvents
    Loop Until loopcount = places Or last = True
        
        
        
     If InStr(divide, ".") > 0 Then
      Do While Right(divide, 1) = "0"
        divide = Left(divide, Len(divide) - 1)
      Loop
    End If
        
    
    
    
    End Function
    
    Public Function sqrt(tnum1 As String) As String
    Dim num1 As String
    num1 = tnum1
    Dim tempnum1 As String
    Dim lastnum As String
    Dim multiply1 As String
    tempnum1 = 2
    lastnum = 1
    
    Do
        'square tempnum
        multiply1 = multiply(tempnum1, tempnum1)
        'if tempnum^2 is bigger than num1 then we know we have found the square root
        If morethan(multiply1, num1) Then Exit Do
        lastnum = tempnum1
        'add the appropriate number to tempnum
        If morethan(subtract(num1, multiply1), 1000000000000#) Then
            tempnum1 = add(tempnum1, 1000000)
        ElseIf morethan(subtract(num1, multiply1), 10000000000#) Then
            tempnum1 = add(tempnum1, 100000)
        ElseIf morethan(subtract(num1, multiply1), 100000000) Then
            tempnum1 = add(tempnum1, 10000)
        ElseIf morethan(subtract(num1, multiply1), 1000000) Then
            tempnum1 = add(tempnum1, 1000)
        ElseIf morethan(subtract(num1, multiply1), 10000) Then
            tempnum1 = add(tempnum1, 100)
        ElseIf morethan(subtract(num1, multiply1), 100) Then
            tempnum1 = add(tempnum1, 10)
        ElseIf morethan(subtract(num1, multiply1), 50) Then
            tempnum1 = add(tempnum1, 5)
        ElseIf morethan(subtract(num1, multiply1), 10) Then
            tempnum1 = add(tempnum1, 3)
        Else
            tempnum1 = add(tempnum1, 1)
        End If
    DoEvents
    Loop
    sqrt = lastnum
    End Function
    
    Public Function Lmod(tnum1 As String, tnum2 As String) As String
    Dim result As String
    Dim num1 As String
    Dim num2 As String
    num1 = tnum1
    num2 = tnum2
    result = 0
    
    Do Until morethan(result, num1)
        result = add(result, num2)
    DoEvents
    Loop
    
    'subtract to get the remainder we're after
    Lmod = subtract(result, num1)
    If Lmod = tnum2 Then Lmod = 0
    
    
    End Function
    
    
    Public Function add(tnum1 As String, tnum2 As String) As String
    Dim num1 As String
    Dim num2 As String
    num1 = tnum1
    num2 = tnum2
    Dim i As Long
    Dim length As Long
    Dim temp As Byte
    Dim carry As Byte
    
    checkdec:
    'check whether the numbers contain a decimal place
    If InStr(num1, ".") > 0 And InStr(num2, ".") > 0 Then
        'if they do then format them so that the decimal place is in the same pasition for both of them
        If (Len(num1) - InStr(num1, ".")) < (Len(num2) - InStr(num2, ".")) Then
            Do
                num1 = num1 & "0"
            Loop Until (Len(num1) - InStr(num1, ".")) = (Len(num2) - InStr(num2, "."))
        ElseIf (Len(num1) - InStr(num1, ".")) > (Len(num2) - InStr(num2, ".")) Then
            Do
                num2 = num2 & "0"
            Loop Until (Len(num1) - InStr(num1, ".")) = (Len(num2) - InStr(num2, "."))
        End If
        
    ElseIf InStr(num1, ".") > 0 And InStr(num2, ".") = 0 Then
        num2 = num2 & "."
        GoTo checkdec
    ElseIf InStr(num1, ".") = 0 And InStr(num2, ".") > 0 Then
        num1 = num1 & "."
        GoTo checkdec
    End If
    
    If Len(num1) > Len(num2) Then
        length = Len(num1)
        num2 = String$(length - Len(num2), "0") & num2
    
    ElseIf Len(num2) > Len(num1) Then
        length = Len(num2)
        num1 = String$(length - Len(num1), "0") & num1
    Else
        length = Len(num1)
    End If
    
    carry = 0
    'start adding the numbers together
    For i = 1 To length
        If Mid(num1, (length - i + 1), 1) = "." Then
            add = "." & add
        Else
            temp = Val(Mid(num1, (length - i + 1), 1)) + Val(Mid(num2, (length - i + 1), 1)) + carry
            If temp < 10 Then
                add = temp & add
                carry = 0
            Else
                add = Right(temp, 1) & add
                carry = Left(temp, 1)
            End If
        End If
    
    Next i
    
    If carry > 0 Then add = carry & add
    
    
        Do While Left(add, 1) = "0"
       add = Right(add, Len(add) - 1)
        Loop
    
    If Left(add, 1) = "." Then add = "0" & add
    
    
    
    End Function
    
    Public Function morethan(tnum1 As String, tnum2 As String) As Boolean
    Dim i As Long
    Dim length As Long
    Dim temp As Byte
    Dim carry As Byte
    Dim num1 As String
    Dim num2 As String
    num1 = tnum1
    num2 = tnum2
    
    checkdec:
    'format just like in add
    If InStr(num1, ".") > 0 And InStr(num2, ".") > 0 Then
        If (Len(num1) - InStr(num1, ".")) < (Len(num2) - InStr(num2, ".")) Then
            Do
                num1 = num1 & "0"
            Loop Until (Len(num1) - InStr(num1, ".")) = (Len(num2) - InStr(num2, "."))
        ElseIf (Len(num1) - InStr(num1, ".")) > (Len(num2) - InStr(num2, ".")) Then
            Do
                num2 = num2 & "0"
            Loop Until (Len(num1) - InStr(num1, ".")) = (Len(num2) - InStr(num2, "."))
        End If
    ElseIf InStr(num1, ".") > 0 And InStr(num2, ".") = 0 Then
        num2 = num2 & "."
        GoTo checkdec
    ElseIf InStr(num1, ".") = 0 And InStr(num2, ".") > 0 Then
        num1 = num1 & "."
        GoTo checkdec
    End If
    
    If Len(num1) > Len(num2) Then
        length = Len(num1)
        num2 = String$(length - Len(num2), "0") & num2
    
    ElseIf Len(num2) > Len(num1) Then
        length = Len(num2)
        num1 = String$(length - Len(num1), "0") & num1
    Else
        length = Len(num1)
    End If
    
    morethan = False
    
    'check if it is more than the other
    For i = 1 To length
        If Mid(num1, i, 1) <> "." Then
        Select Case Val(Mid(num1, i, 1))
            Case Is > Val(Mid(num2, i, 1))
                morethan = True
                Exit Function
            Case Is < Val(Mid(num2, i, 1))
                morethan = False
                Exit Function
            End Select
        End If
    
    Next i
    
    End Function
    continued in next post
    Last edited by killo; Feb 27th, 2008 at 11:30 AM.

  2. #2

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Re: Working with BIG numbers or LOTS of decimal places

    Code:
    Public Function subtract(tnum1 As String, tnum2 As String) As String
    Dim i As Long
    Dim length As Long
    Dim temp As Integer
    Dim carry As Byte
    Dim num1 As String
    Dim num2 As String
    num1 = tnum1
    num2 = tnum2
    checkdec:
    'format like always
    If InStr(num1, ".") > 0 And InStr(num2, ".") > 0 Then
        If (Len(num1) - InStr(num1, ".")) < (Len(num2) - InStr(num2, ".")) Then
            Do
                num1 = num1 & "0"
            Loop Until (Len(num1) - InStr(num1, ".")) = (Len(num2) - InStr(num2, "."))
        ElseIf (Len(num1) - InStr(num1, ".")) > (Len(num2) - InStr(num2, ".")) Then
            Do
                num2 = num2 & "0"
            Loop Until (Len(num1) - InStr(num1, ".")) = (Len(num2) - InStr(num2, "."))
        End If
    ElseIf InStr(num1, ".") > 0 And InStr(num2, ".") = 0 Then
        num2 = num2 & "."
        GoTo checkdec
    ElseIf InStr(num1, ".") = 0 And InStr(num2, ".") > 0 Then
        num1 = num1 & "."
        GoTo checkdec
    End If
    
    If Len(num1) > Len(num2) Then
        length = Len(num1)
        num2 = String$(length - Len(num2), "0") & num2
    ElseIf Len(num2) > Len(num1) Then
        length = Len(num2)
        num1 = String$(length - Len(num1), "0") & num1
    Else
        length = Len(num1)
    End If
    
    'subtract the numbers in a similar way to the add code
    carry = 0
    For i = 1 To length
        If Mid(num1, (length - i + 1), 1) = "." Then
            subtract = "." & subtract
        Else
            temp = Val(Mid(num1, (length - i + 1), 1)) - Val(Mid(num2, (length - i + 1), 1)) - carry
            If temp >= 0 Then
                subtract = temp & subtract
                carry = 0
            ElseIf temp < 0 Then
                carry = 1
                temp = temp + 10
                If temp < 0 Then
                    temp = temp + 10
                    carry = 2
                End If
                subtract = temp & subtract
            End If
        End If
    
    Next i
    
    Do While Left(subtract, 1) = "0"
     subtract = Right(subtract, Len(subtract) - 1)
    Loop
    
    If Left(subtract, 1) = "." Then subtract = "0" & subtract
    
    
    
    End Function
    
    
    
    
    
    
    Public Function multiply(tnum1 As String, tnum2 As String) As String
    Dim num1 As String
    Dim num2 As String
    
    
    Dim tempnum3 As String
    Dim mcounter As String
    Dim tempnum2 As String
    Dim templeft As String
    Dim tempright As String
    Dim tempnum1 As String
    
    If morethan(tnum1, tnum2) Then
        num2 = tnum1
        num1 = tnum2
    Else
    num1 = tnum1
    num2 = tnum2
    End If
    
    If InStr(num2, ".") > 0 Then
        If Left(num2, 2) = "0." Then
            'extract 38 and 0.45 from 38.45 for example
            tempnum2 = num2
            num2 = 0
        Else
        tempnum2 = "0." & Right(num2, (Len(num2) - InStr(num2, ".")))
        num2 = Left(num2, (InStr(num2, ".")) - 1)
    End If
    tempnum1 = num1
    
    'once they have been extracted, the decimal places need to be moved
    'turn 6.42 * 0.34 into 34 * 0.0642 for example
    'this will give the same result, but the multiplication code needs at least one of the numbers to be whole for it to work
    'so that is why this needs to be done
    If InStr(tempnum1, ".") = 0 Then tempnum1 = tempnum1 & "."
        Do
            templeft = Left(tempnum1, (InStr(tempnum1, ".") - 1))
            tempright = Right(tempnum1, (Len(tempnum1) - (InStr(tempnum1, "."))))
            If Len(templeft) = 1 Then templeft = 0 & templeft
            tempright = Right(templeft, 1) & tempright
            templeft = Left(templeft, Len(templeft) - 1)
            tempnum1 = templeft & "." & tempright
            templeft = Left(tempnum2, (InStr(tempnum2, ".") - 1))
            tempright = Right(tempnum2, (Len(tempnum2) - (InStr(tempnum2, "."))))
            templeft = templeft & Left(tempright, 1)
            tempright = Right(tempright, Len(tempright) - 1)
            tempnum2 = templeft & "." & tempright
        Loop Until Right(tempnum2, 1) = "."
        tempnum2 = Left(tempnum2, Len(tempnum2) - 1)
        Do While Left(tempnum2, 1) = "0"
            tempnum2 = Right(tempnum2, Len(tempnum2) - 1)
        Loop
    
    'multiply just the 0.?? for now
        Do Until mcounter = tempnum2
            multiply = add(multiply, tempnum1)
            mcounter = add(mcounter, 1)
    DoEvents
        Loop
    End If
    
    'swap the numbers if one is bigger than the other so that the multiplication code doesn't need to loop around so much
    If morethan(num2, num1) And InStr(num1, ".") = 0 Then
        tempnum3 = num1
        num1 = num2
        num2 = tempnum3
    End If
    'multiply the whole numbers
    mcounter = 0
    Do Until mcounter = num2
        multiply = add(multiply, num1)
        mcounter = add(mcounter, 1)
    Loop
    
    'remove any unnecessary 0's at the right if there is a decimal place
    If InStr(multiply, ".") > 0 Then
        Do While Right(multiply, 1) = "0"
             multiply = Left(multiply, Len(multiply) - 1)
        Loop
    End If
    
    'remove any unnecessary 0's at the left
    
    Do While Left(multiply, 1) = "0"
        multiply = Right(multiply, Len(multiply) - 1)
    Loop
    
    If Left(multiply, 1) = "." Then multiply = "0" & multiply
    
    End Function
    
    
    Public Function power(tnum1 As String, tnum2 As String) As String
    Dim pcounter As Long
    Dim num1 As String
    Dim num2 As String
    num1 = tnum1
    num2 = tnum2
    power = 1
    
    Do
        'multiply the number by itself the necessary amount of times
        power = multiply(power, num1)
        pcounter = pcounter + 1
    
    Loop Until pcounter = num2
    
    End Function
    Attached Files Attached Files
    Last edited by killo; Feb 27th, 2008 at 11:31 AM.

  3. #3
    Frenzied Member
    Join Date
    Dec 2007
    Posts
    1,071

    Re: Working with BIG numbers or LOTS of decimal places

    Power coding, just learn to indent =]

  4. #4

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Re: Working with BIG numbers or LOTS of decimal places

    forgot about that, i'll have to get into that habit. i'll indent it all tomorrow.

  5. #5
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    the limit to how big a number they can handle is not 1.79769313486232E+308 which is the normal double limit, but 1.79769313486232E+308 DIGITS LONG!
    Have you actually tried using numbers that large? I suspect you will get an error much sooner, partly because of the limit of the String data type:
    Quote Originally Posted by VB help
    A variable-length string can contain up to approximately 2 billion (2^31) characters.
    ..and partly due to the total RAM available. A string of the maximum size takes around 2GB, and you often have two copies of each String (such as when you call the Subtract function), so could easily be using over 4GB of RAM .

    it also needs some work as i know they can be alot faster, any suggestions to make them faster will be greatly appreciated.
    I haven't read much of your code, as it is not indented, and therefore very hard to read. However, there are some things that jumped out at me.

    Due to the size limit for Strings, you could use Long variables for the loop counters (and length variables etc). This should make things faster (as a Long is simpler, and the native data type for the CPU).

    In a few places you have code like this: Left(Right(num1, i), 1) , which is exactly the same as this: Mid(num1, i, 1) . As calling functions is relatively slow, changing this should give a noticeable speed boost when used in loops.

    You have lots of redundant code, for example this section of your "divide" function:
    Code:
    If InStr(divide, ".") > 0 And Right(divide, 1) = "0" Then
    Do
    If Right(divide, 1) = "0" Then divide = Left(divide, Len(divide) - 1)
    Loop Until Right(divide, 1) <> "0"
    End If
    Is equivalent to this faster version:
    Code:
    If InStr(divide, ".") > 0 Then
      Do While Right(divide, 1) = "0"
        divide = Left(divide, Len(divide) - 1)
      Loop
    End If
    There are several other tips on making your code faster I could mention (such as $ versions of string functions) , but most of them can be found in the "Optimisation" section of our Classic VB FAQs (in the FAQ forum, which is shown near the top of our home page)

    For an even larger speed increase you could move to using Byte arrays instead of Strings, but you are likely to find that confusing.

  6. #6

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Re: Working with BIG numbers or LOTS of decimal places

    thanks for that, yes i figured this would be limited by available RAM. i'll indent and apply your improvements tomorrow. (going to bed now)
    I think i understand what you are saying about byte arrays. the string is split up one character at a time to a byte array and instead of using Mid(num1, i, 1) i just use num1(i)
    correct?
    Last edited by killo; Feb 24th, 2008 at 06:33 PM.

  7. #7
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: Working with BIG numbers or LOTS of decimal places

    For realistic speed, just imagine to do a simple division with your divive() function:
    Code:
    Public Function divide(tnum1 As String, tnum2 As String, tplaces As String) As String
    Code:
    Result = divide(String(2^31-1, "9"), "2", "1")
    '--tnum1 is a String with 2,147,483,647 digits divide by tnum2 = "2"
    That will call 1,073,741,824 times to the lengthy and complicated function add() and also call 1,073,741,824 times to the lengthy and complicated function morethan(), plus many other calls to functions subtract() and multiply().

    Can anybody tell me how long this process will take?
    I guess may be a few days. The time will be double if replace "2" by "1".
    * For division, you should use the approx guess method (that you learnt in primary school) instead of add or subtract then compare one by one.

    No time to comment on other functions.

    I don't think anyone will interest in your functions.

    Edit:
    The figure I mentioned above is incorrect.
    Instead of 1,073,741,824 it should be : 5*10^(2^31-2) = 5*10^2147483646. It will take a thousand years perhaps.
    Last edited by anhn; Feb 27th, 2008 at 06:13 PM.
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    Baby Steps a guided tour
    IsDigits() and IsNumber() functions Wichmann-Hill Random() function >> and << functions for VB CopyFileByChunk

  8. #8
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    I didn't notice this edit before (I guess I looked just before you posted it):
    Quote Originally Posted by killo
    the string is split up one character at a time to a byte array and instead of using Mid(num1, i, 1) i just use num1(i)
    correct?
    That is basically it, yes. Unfortunately you will also need to convert to/from strings.

    Based on your current methods, I would recommend doing that later - as things currently stand, you will actually get much bigger speed improvements by changing your methods, such as anhn's suggestion of "approx guess" for divide.

    Your "morethan" function can also be made significantly quicker for most situations, by simply checking how many digits there are before the decimal point. If there is a difference, you can immediately tell which is bigger (thus skip the rest of the routine); there are several improvements that can be made in the rest of the code too (eg: in addition to what is mentioned in the FAQs, make use of the String$ function - or even better, don't change the strings at all).


    I notice that most of your routines make copies of the strings which are passed to them, so you are basically doubling the amount of RAM required at each stage (but divide calls multiply which calls add, so you are storing 6 extra copies!).. which makes the need for Virtual Memory much more likely, and if it is needed, the entire computer (and thus your program) will suddenly be about 10 times slower!

  9. #9

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Re: Working with BIG numbers or LOTS of decimal places

    i applied your improvements suggested in your last post & indented & included a sample project which uses this module to calculate pi to however many decimal places you specify.
    i understand what you're saying about the morethan function i'll modify that soon.
    what do you mean about the string$ function, i have never heard of this function before, could you explain to me please?
    i don't know what you mean by approximate guess method for divide maybe i learnt it but not by this name, could someone tell me what this is too?

    what you are saying about the copies, i need to do this because if i call say:
    number2 = divide(number1,4) then the divide function changes number1 when i don't want it to. but if i say num1 = tnum1 then i can mess around with num1 as much as i want without it changing tnum1 because if it changes tnum1 then it's going to change the variable used in the function (number1) which i don't want it to. if theres any way i can stop it from changing it then I'll do it but i don't know for now.
    about my functions calling other of my functions - they need to since i can't use regular add in the multiply function for example as it's supposed to be working with large numbers and an ordinary add function could overflow, so they need to call eachother.
    thanks for the help people.

  10. #10
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    I understand why you are using copies, and there isn't an easy fix unfortunately.. you need to fundamentally change the way the routines work. For example, with "morethan" you don't need to modify anything - you can just check in two stages (up to the decimal point, then [if apt] after it).

    For the 'approximate guess' method, it would be best to find a tutorial that explains it, and then convert the method into code.

    The String$ function (note the $, as explained in the FAQ article on optimisation) creates a string with repeating digits, for example String$(5, "A") creates "AAAAA". By using that, you can change this section of morethan:
    Code:
    If Len(num1) > Len(num2) Then
        length = Len(num1)
        Do
            num2 = "0" & num2
        Loop Until Len(num2) = length
    to this:
    Code:
    If Len(num1) > Len(num2) Then
        length = Len(num1)
        num2 = String$(length - Len(num2), "0") & num2
    I have created a simple test program to run multiple versions of MoreThan, and have compared your two versions.. for a string of 100,000 digits, the time taken drops from around 27 seconds for the original to around 0.4 seconds! (and as far as I can tell, the only difference is the Double variables have become Long). The speed of this can be roughly doubled again, by using a Select case in the final loop (rather than two If's which check essentially the same thing).

    Oh, and note that there is no need for GoTo's (which make the code harder to read). For example, this (again in MoreThan):
    Code:
    If Mid(num1, i, 1) = "." Then GoTo nexty
    ...
    nexty:
    should be like this instead:
    Code:
    If Mid(num1, i, 1) <> "." Then 
        ...
    End If

  11. #11

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Re: Working with BIG numbers or LOTS of decimal places

    ok, updated using the string$ function
    select case used in more than
    goto's removed
    some other improvements

    i can't find anything to do with approximate guess on google though?
    and it still takes about 45 seconds to calculate just 50 decimal places of pi on my 2.8ghz dual core

  12. #12
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    Can you show/attach your current code, particularly the MoreThan routine?

    I've still got my test app, which includes my own version. When the last one you posted takes 35 seconds, mine takes at most 10s - and if the number of digits before the decimal place differs, it takes just 0.05s.

    The majority of this gain comes from things I've already mentioned, and I'd like to see what you've done so I can explain the changes as apt - as they can be used in other parts of the code too.


    I just did a search for an explanation of the approximate guess method, but couldn't find it.. from a quick glance it seems like these might be useful:
    http://en.wikipedia.org/wiki/Division_%28mathematics%29
    http://www.mathpath.org/Algor/algor.long.div.htm

  13. #13

    Thread Starter
    Fanatic Member
    Join Date
    May 2005
    Posts
    528

    Re: Working with BIG numbers or LOTS of decimal places

    the code on the first two posts is the most recent.

  14. #14
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    Ah, OK.. as that code was last updated a week before your post (and it still contains dreaded GoTo's which you said you removed), I assumed that it wasn't the latest.

    There was also only limited use of the String$ function - just duplicating my example, rather than also using it in the "format" sections (where the code was virtually identical). When you are given a tip, think about the other places where it can be used, rather than just the specific example you were given.


    As far as the Select Case goes, what you have now does 25% less work than what you had before (as you only run Val(Mid(num1, i, 1)) once rather than twice), but it can be improved by the same amount again (thus only 50% of the original work) if you also only run Val(Mid(num2, i, 1)) once. To do this, subtract one from the other, then compare the result to 0, ie:
    Code:
        Select Case Val(Mid$(num1, i, 1)) - Val(Mid$(num2, i, 1))
        Case Is > 0  
                morethan = True
                Exit Function
        Case Is < 0
    Note the use of $ here too, which improves the speed again - and should be used for all of the string-based functions that support it (like Left/Right/Trim/etc)


    There is another improvement you can make to the speed of the loop, which is to remove the If statement - and instead have two copies of the loop (one which checks up to the ".", and one which checks after it). Running a single If is fairly quick, but when it is in a loop (especially one like this which will run many times) the time builds up.


    These last few tips are a large part of why the worst time for my version is so much faster than what you've currently got.. but another is that I made use of something I mentioned before, which is to not make copies of the string.

    As far as I can see, there is absolutely no need to have the "format" section (which is why you create copies of the strings). You are doing it so that you can compare the correct digits with each other, but the same could be done with simple maths (check the position of the dot in each number, and store the difference - then use that value in your loop [eg: Mid$(num2, i + diff, 1)] ).

    That is only one way to deal with it, and I didn't actually use it here, due to an extension of something I mentioned earlier:
    Your "morethan" function can also be made significantly quicker for most situations, by simply checking how many digits there are before the decimal point. If there is a difference, you can immediately tell which is bigger (thus skip the rest of the routine);
    This is a nice special case, which allows you to skip all of the code after the two calls to InStr, just by using one simple If statement. This is why the fastest time for my version is so low - it is doing almost no work!

    Adding this should improve the speed of the Divide/Sqrt/Lmod functions, as they all call this routine repeatedly, usually with different length numbers.

    There are some other special cases for this function, which I have commented in the code (attached below).


    This routine can still be improved further, but only by relatively small amounts - so it would be better to focus on the other functions instead, as they can also be improved dramatically. Part of this will be by using the same ideas as I've explained so far, but even more by thinking of alternative ways of doing things - just because something works, it doesn't mean that it is the best (or fastest) way.

    One example of this is in Sqrt you call subtract(num1, multiply1) up to 8 times when the variables haven't changed - instead, store the result of that call to a variable, and use the variable in your If statements. There may well be even better ways to find a Sqrt, so try searching the web for algorithms.


    For the size of numbers you are using in your test (just 50 digits) the speed gains from implementing the methods I have described may not be dramatic, but I think the gain will be huge as the size of numbers increases (especially if you get close to using up the physical RAM, in which case not creating copies of the strings will make things 10+ times faster).

    For these smaller numbers, you are likely to get a decent impact from using Byte arrays.. and even more if you create your own data type (consisting of two byte arrays, one for the integer part and one for the decimals) which you pass to each of the routines. That would take a bit more effort to code, and would take more effort to set up/output the numbers (I'd recommend creating "CreateFromString" and "ExportToString" routines), but would mean that the actual worker functions (add etc) would be much faster.
    Attached Files Attached Files

  15. #15
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: Working with BIG numbers or LOTS of decimal places

    New version 13-03-2008: There is no String copying.

    This is my much shorter and faster version of function MoreThan():

    Pre:
    * sNum1 and sNum2 contain only digits and zero or one decimal dot "."
    * Depends on available memory, sNum1 and sNum2 may not be too large such as with more than 10^8 digits.
    Code:
    Public Function MoreThan(sNum1 As String, sNum2 As String) As Boolean
       Dim Dot1 As Long, Dot2 As Long
       
       Dot1 = InStr(sNum1, "."): If Dot1 = 0 Then Dot1 = Len(sNum1) + 1
       Dot2 = InStr(sNum2, "."): If Dot2 = 0 Then Dot2 = Len(sNum2) + 1
       If Dot1 = Dot2 Then
          '-- 2 integer parts have the same length, just simply compare 2 strings
          'MoreThan = (StrComp(sNum1, sNum2, vbBinaryCompare) = 1)
          MoreThan = (sNum1 > sNum2)
       Else
          MoreThan = (Dot1 > Dot2)
       End If
    End Function
    I recommend to create a function called BigComp() similar as StrComp() function then based on this function
    you can have all other useful comparision functions GT(), GTE(), LT() and LTE().
    Code:
    Public Function BigComp(sNum1 As String, sNum2 As String) As Integer
       Dim Dot1 As Long, Dot2 As Long
       
       Dot1 = InStr(sNum1, "."): If Dot1 = 0 Then Dot1 = Len(sNum1) + 1
       Dot2 = InStr(sNum2, "."): If Dot2 = 0 Then Dot2 = Len(sNum2) + 1
       If Dot1 = Dot2 Then
          '-- 2 integer parts have the same length, just simply compare 2 strings
          BigComp = StrComp(sNum1, sNum2, vbBinaryCompare)
       Else
          BigComp = Sgn(Dot1 - Dot2)
       End If
    End Function
    Code:
    Public Function GT(sNum1 As String, sNum2 As String) As Boolean
       GT = (BigComp(sNum1, sNum2) = 1)
    End Function
    
    Public Function GTE(sNum1 As String, sNum2 As String) As Boolean
       GTE = (BigComp(sNum1, sNum2) > -1)
    End Function
    
    Public Function LT(sNum1 As String, sNum2 As String) As Boolean
       LT = (BigComp(sNum1, sNum2) = -1)
    End Function
    
    Public Function LTE(sNum1 As String, sNum2 As String) As Boolean
       LTE = (BigComp(sNum1, sNum2) < 1)
    End Function
    Coding suggestion: To make your code easier to read, beside of indenting, you should use combination of UpperCase and LowerCase when naming variables or functions or subs. Don't be lazy on this, for each of them you need to do only once.
    Last edited by anhn; Mar 12th, 2008 at 06:58 PM.
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    Baby Steps a guided tour
    IsDigits() and IsNumber() functions Wichmann-Hill Random() function >> and << functions for VB CopyFileByChunk

  16. #16
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    I like that, but found that the speed was extremely similar to mine (generally marginally slower than mine in the cases I tested), but there may be different kinds of tests where yours is noticeably better.

    There is a very serious exception to the speed similarity, which is when the numbers become really big (so you approach/need virtual memory). The speed of yours degrades terribly (as it is using Mid to create copies of large chunks of the strings), whereas mine degrades much later and at a lower rate (as it only creates copies of 1 character of each string at a time).


    The idea of using BigComp etc is good, as it provides more functionality.. but if the numbers used will actually be large, BigComp should be re-written to avoid copying large chunks of the strings.

  17. #17
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: Working with BIG numbers or LOTS of decimal places

    I updated Post#15 with newer version:
    That is shorter and faster again and without String copying.
    We just simply use StrComp() when 2 integer parts have the same length.

    killo's project lacks of negative numbers and Subtract(s1,s2) gives wrong result if s1 "<" s2.
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    Baby Steps a guided tour
    IsDigits() and IsNumber() functions Wichmann-Hill Random() function >> and << functions for VB CopyFileByChunk

  18. #18
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    In terms of speed, those changes will be great.. but there is a minor issue with accuracy, which was dealt with in my version.

    The issue is where sNum1 and sNum2 both have equal characters (including a decimal point), except sNum1 has an extra 0 on the end, eg: sNum1 = "12.30" and sNum2 = "12.3".

    We can see they are equal in terms of value (thus sNum1 is not "MoreThan" sNum2), but a direct string comparison will see sNum1 as "more".


    You've made me think about it tho, and I can now see that as long as Len(sNum1) <= Len(sNum2) , it would be safe to do that (as sNum2 having extra 0's means sNum1 is not "MoreThan" it).

    This means that my code could be made faster (when the second number has extra decimal places) with an extra character:
    Code:
    ElseIf Len(tnum1) <= Len(tnum2) Then

    However.. this is all relatively academic, as the other routines (such as Add and Subtract) cannot be improved as dramatically, and require a major re-think to get equivalent gains (like perhaps a UDT or class).

  19. #19
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: Working with BIG numbers or LOTS of decimal places

    You are right. At first I thought about the leading 0's but no problem with that. Now you point out the trailing 0's.
    Some where in killo's code he has a loop to remove trailing 0's after dot, so the supplied numbers must be in "proper" format.

    I think you and I did some modifications of small parts in his project just to give him some samples of coding he should learn and think when he write the code.

    No way to make the current code becomes useful to anyone as it will take a few months to rewrite everything.
    The simple way is to use a UDT with array for BigNumbers and use much larger base instead of base-10. With Decimal subtype (upto 29 digits) we can safely use base-10^14. (VB6/VBA does not have the luxury of Int64).
    I just tried to do divide(String$(1000, "1"), "13", 20) and it forces me to kill the process as it may take many hours if not many days.
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    Baby Steps a guided tour
    IsDigits() and IsNumber() functions Wichmann-Hill Random() function >> and << functions for VB CopyFileByChunk

  20. #20
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    Quote Originally Posted by anhn
    You are right. At first I thought about the leading 0's but no problem with that. Now you point out the trailing 0's.
    Some where in killo's code he has a loop to remove trailing 0's after dot, so the supplied numbers must be in "proper" format.
    True, when that routine is called by others (assuming they keep the formatting sections) it is fine.. but it does need to be dealt with in case the routine is called directly from other code.
    I think you and I did some modifications of small parts in his project just to give him some samples of coding he should learn and think when he write the code.
    Absolutely - and it's good to swap ideas too
    The simple way is to use a UDT with array for BigNumbers and use much larger base instead of base-10. With Decimal subtype (upto 29 digits) we can safely use base-10^14. (VB6/VBA does not have the luxury of Int64).
    Using the Decimal data type sounds good in terms of size per element, but unfortunately it is terrible in terms of speed when compared to other numeric types.

    For best speed you could use Long, but the exact data type needs thinking about.. for example: can you safely add two together? (if so, will you need to use a slower type to allow it?)

    In terms of overall memory usage, all numeric types (assuming you use them to the limits) will be virtually identical - except for Byte which does not allow negative numbers, and as such allows you to half the memory requirements.

  21. #21
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: Working with BIG numbers or LOTS of decimal places

    I did another project on factorial and see that between Decimal and Long, Decimal (up to 29 digits, can use base-10^14) will take advantage because even it is slower than Long (up to 10 digits, can use base-10^4) but for overall is has much less elements to deal with so it becomes much faster (particularly with multiply and division).

    In VB.NET with Int64 (up to 20 digits, can use base-10^9) that is closer to Decimal so may be Int64 will be better than Decimal.

    For me, memory usage is the second priority. The top priority must be speed.
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    Baby Steps a guided tour
    IsDigits() and IsNumber() functions Wichmann-Hill Random() function >> and << functions for VB CopyFileByChunk

  22. #22
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,265

    Re: Working with BIG numbers or LOTS of decimal places

    That's a fair point, I can see how fewer elements would help with multiply and divide (but perhaps the opposite for add and subtract?).

    The only minor issue is that when you get really big numbers, the memory usage severely effects the speed... but with the change of data type, that would probably be after billions of digits, so can almost certainly be ignored!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width