Bay Six Software Forum Index Bay Six Software
Beyond the Basics
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

[Case Study] Number of digits in an integer

 
Post new topic   Reply to topic    Bay Six Software Forum Index -> Code Optimization
View previous topic :: View next topic  
Author Message
Brent
Site Admin


Joined: 01 Jul 2005
Posts: 729

PostPosted: Jun 20th, 2007, 9:22am    Post subject: [Case Study] Number of digits in an integer Reply with quote

This is a case study for finding the fastest way to calculate the number of digits in a whole number. One does this to format numbers in a column (e.g. centering or right justifying).

In the code below, all of the test cases are commented out. Besides that, each case is given a line number and placed in the order of fastest to slowest, as benchmarked by me. The times I got are placed in comments after each case. The non-approximate times are average times over 5 runs of that case.

I would encourage you to do your own testing of each case to confirm my results. Per case times on different PCs are meaningless. The only significance is in comparing each case to the others.

To test each case, uncomment just that line and run the program. The time in milliseconds will eventually appear in the main window. To maintain consistancy, please try to keep background applications to a minimum, especially media players and the like that may place varying loads on the CPU.

I conclude that the obvious method (case #8) is not the fastest way to compute the number of digits in a number. As I've stated before, strings cost a lot of CPU cycles. Additionally, the prettiest methods, the function calls (#9 and #10), turn out to be far worse than any inline code do to the overhead of a function call. The fastest method (#1) is an eye-opener because it is counter-intuitive. It shows that a run-time computation can be, on average, faster than a variable holding that same value, computed even before the time started. Despite this anomaly, the precomputed value of log(10) in many of the leaders shows that precomputing constants is generally the thing to try when you are attempting to optimize code for speed. Still, given the closeness in the times between #1 and #2, others' tests might flip these twp.

Another conclusion I draw from these tests is that global variables are slower than local variables, even in the main program block. This is another odd situation with a non-intuitive result. I have no idea at this moment why the scope of a variable should have such a drastic effect on the execution speed.

Please note that most of the given cases are not robust and require an input that is a counting number--zero and negative numbers will cause the program to crash in the absense of an ON ERROR. Cases #7 and #10 will accept any integer value. But unlike #8, which will count the minus sign in the number, the previously mentioned cases do not. This was done to keep this clean and clear.

I welcome your comments and would like very much to know if your results are different for mine.
Code:
    n = 123456789

    Global g.LogOf10, g.Big1
    LogOf10 = Log(10) : g.LogOf10 = LogOf10
    Big1 = 1 + 1e-300 : g.Big1 = Big1
    Epsilon = 1e-300

    t = Time$("ms")

    For i = 1 To 1000000
' 1     c = Int(Log(n) / LogOf10 + 1 + 1e-300) ' 9.328s
' 2     c = Int(Log(n) / LogOf10 + Big1) ' 9.4032s
' 3     c = Int(Log(n) / Log(10) + Big1) ' 11.6186s
' 4     c = Int(Log(n) / Log(10) + 1 + 1e-300) ' 11.6846s
' 5     c = Int(Log(n) / LogOf10 + 1 + Epsilon) ' 11.756s
' 6     c = Int(Log(n) / g.LogOf10 + g.Big1) ' ~14.5s
' 7     If n Then c = Int(Log(Abs(n)) / LogOf10 + 1 + 1e-300) Else c = 1 ' ~15.5s
' 8     c = Len(Str$(n)) ' ~16s
' 9     c = CountingDigits(n) ' ~51s
'10     c = NumberOfDigits(n) ' ~60s
    Next

    Print Time$("ms") - t
    'Print c

    End

Function CountingDigits ( Num )
    CountingDigits = Int(Log(Num) / Log(10) + 1 + 1e-300)
End Function

Function NumberOfDigits ( Num )
    If Num Then NumberOfDigits = Int(Log(Abs(Num)) / Log(10) + 1 + 1e-300) Else NumberOfDigits = 1
End Function

_________________
Brent
Back to top
View user's profile Send private message Send e-mail
Fish
Guest





PostPosted: Sep 9th, 2007, 11:45am    Post subject: Re: [Case Study] Number of digits in an integer Reply with quote

Do you mean like count the length of a number? In which case you can use str$() and len()
Back to top
Brent
Site Admin


Joined: 01 Jul 2005
Posts: 729

PostPosted: Sep 9th, 2007, 7:22pm    Post subject: Re: [Case Study] Number of digits in an integer Reply with quote

Did you not see the line of
Code:
' 8     c = Len(Str$(n)) ' ~16s
?
_________________
Brent
Back to top
View user's profile Send private message Send e-mail
Fish
Guest





PostPosted: Sep 11th, 2007, 8:42am    Post subject: Re: [Case Study] Number of digits in an integer Reply with quote

Brent wrote:
Did you not see the line of
Code:
' 8     c = Len(Str$(n)) ' ~16s
?


Wouldn't that be all you need?

EDIT: Never mind, I get it now
Back to top
RichardRussell
Full Member


Joined: 28 Jan 2012
Posts: 57
Location: Downham Market, UK

PostPosted: Feb 4th, 2012, 6:59pm    Post subject: Re: [Case Study] Number of digits in an integer Reply with quote

Brent wrote:
I welcome your comments and would like very much to know if your results are different for mine.

I thought it might be of interest to compare the results from LB 4.04 (first column) with those from LBB 1.70 (second column):

Code:
Method 1:   9.0   8.4
Method 2:   9.1   7.5
Method 3:  10.1   8.0
Method 4:   9.8   8.9
Method 5:  10.0   7.9
Method 6:  13.4   7.6
Method 7:  14.0   8.7
Method 8:  11.9   2.8
Method 9:  39.9  10.8
Method 10: 46.8  13.2

Perhaps in due course LB5 can be added to the comparison!

Richard.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Bay Six Software Forum Index -> Code Optimization All times are GMT
Page 1 of 1
Jump to:  
Quick Reply
Username:
Message:
   Shortcut keys: Alt+Q to activate, Alt+P to preview, Alt+S to submit
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum



Lo-Fi Version
Powered by phpBB © 2001, 2005 phpBB Group