
Bay Six Software Beyond the Basics

View previous topic :: View next topic 
Author 
Message 
Brent Site Admin
Joined: 01 Jul 2005 Posts: 746

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


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 nonapproximate 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 eyeopener because it is counterintuitive. It shows that a runtime 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 nonintuitive 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 numberzero 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 + 1e300 : g.Big1 = Big1
Epsilon = 1e300
t = Time$("ms")
For i = 1 To 1000000
' 1 c = Int(Log(n) / LogOf10 + 1 + 1e300) ' 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 + 1e300) ' 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 + 1e300) 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 + 1e300)
End Function
Function NumberOfDigits ( Num )
If Num Then NumberOfDigits = Int(Log(Abs(Num)) / Log(10) + 1 + 1e300) Else NumberOfDigits = 1
End Function 
_________________ Brent 

Back to top 


Fish Guest

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


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: 746

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


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

Back to top 


Fish Guest

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


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

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


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 







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

