| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 561.1 | | CLT::GILBERT | eager like a child | Fri Aug 08 1986 16:05 | 6 |
| digits := 1; temp := 10;
while x >= temp do
begin
digits := digits + 1;
temp := temp * 10;
end;
|
| 561.2 | What HLL's do you know? | MODEL::YARBROUGH | | Fri Aug 08 1986 16:26 | 5 |
| (In Fortran:)
INTEGER digits
REAL X
...
digits = ALOG10(X)+1.
|
| 561.3 | The fastest solution | EAGLE7::DANTOWITZ | David .. DTN: 226-6957 -- LTN2-1/H07 | Fri Aug 08 1986 17:32 | 14 |
|
I was looking for a QUICK algorithm that would be faster
than the following:
IF X LSS 10 then 0
else IF X LSS 100 then 1
else IF X LSS 1000 then 2
etc ... I suppose that this is the fastest.
|
| 561.4 | Just a thought | VIRTUE::HALLYB | Free the quarks! | Fri Aug 08 1986 19:00 | 8 |
| Sounds like microcode being developed here. OK, is this a 32-bit
unsigned integer? 31 bits including sign? Any chance of parallel
threads of execution? For example, since 10^3 ~= 2^10 I would guess
you have a chance of splitting the problem into 22 left bits and
10 right bits. If all 22 left bits are zero, you could look up
the answer in a small RAM. If any left 22 bits are nonzero, you
could solve the problem for 22 left bits and add 3. It all depends
on how the bits fall.
|
| 561.5 | | CLT::GILBERT | eager like a child | Fri Aug 08 1986 19:38 | 15 |
| How about :-)
if x lss 10^8 then
if x lss 10^4 then
if x lss 10^2 then
if x lss 10^1 then 0 else 1
else
if x lss 10^3 then 2 else 3
else
if x lss 10^6 then
if x lss 10^5 then 4 else 5
else
if x lss 10^7 then 6 else 7
else
...
|
| 561.6 | ?Data Type? | CHOVAX::YOUNG | Chi-Square | Sat Aug 09 1986 13:16 | 8 |
| One question:
What is the data type of X? Signed longword, Unsigned word, Real
type-F, Real type-G, etc..? This is very important for finding the
fastest algorithim.
-- Barry
|
| 561.7 | ?Distribution? | CHOVAX::YOUNG | Chi-Square | Sat Aug 09 1986 13:36 | 15 |
| Another question:
Did you want the fastest routine for a particular distribution?
Usually uniform, but maybe reverse exponential? Since in uniform
distribution, those longwords with 10 digits outnumber all those
with less than 10 digits COMBINED, this can be very important.
Reverse exponential, on the other hand, would assume that there
is an equal chance of the number being a 1 digit, or 2 digit, ...
or 10 digit number.
Or, did you in fact just want the fastest algorithim based on O
notation? : O(log i), O(i), O(k), ... etc.
-- Barry
|
| 561.8 | A solution. | CHOVAX::YOUNG | Chi-Square | Sat Aug 09 1986 15:09 | 25 |
| I have tested all the algorithm presented here, with the exception
of the microcode suggestion. I have assumed longword signed integers
with uniform distribution.
I believe that the fastest algorithim is the one that you listed,
David, except that you should reverse the order of your tests.
That is, test for >= 10^9 first, then >= 10^8, et cetera:
If (x .ge. 10^9) then digits = 10
Else if (x .ge. 10^8) then digits = 9
.
.
.
Else if (x .ge. 10^1) then digits = 2
Else digits = 1
End if
Using Fortran on a 780, this routine takes ~4.5 microseconds, as
opposed to ~6.5 microseconds for Peters second routine (the next
fastest), and ~23 microseconds for your original routine.
I have the sources of these tests if you want them.
-- Barry
|
| 561.9 | Thanks | EAGLEA::DANTOWITZ | David .. DTN: 226-6957 -- LTN2-1/H07 | Sun Aug 10 1986 11:38 | 16 |
|
The reason for my query is because I need to know the log base
10 for a conversion routine. (32-bits to decimal digits ...
no microcode.) The RTL routines like to right justify such
conversions, so you end up with spaces. Rather than searching for
the first non-space I decided it's quicker to figure out how many
digits you SHOULD have - thus my question.
The distribution is currently not known. Basically there will be
quite a lot in the 0 to 100 and some others that may be higher.
It's not uniform but will most likely be biased to the 0-100 range
(~60% - I'm guessing)
Thanks for the help.
David
|
| 561.10 | Tweak to do negative numbers also... | TLE::BRETT | | Mon Aug 11 1986 17:11 | 87 |
| I know you said "in a hll, not MACRO", but I never could obey
instructions and the following is almost certainly expressible in
your chosen language (although FORTRAN/COBOL/BASIC may have fun...)
/Bevin
.entry Z_LOG10,^m<r2>
movl @4(ap),r2
cvtld r2,r0
extzv #7,#7,r0,r1
movzbl L_TABLE[r1],r0
cmpl r2,N_TABLE[r1]
bleq 10$
incl r0
10$:ret
N_TABLE:
.long 0
.long 9
.long 9
.long 9
.long 9
.long 9
.long 9
.long 99
.long 99
.long 99
.long 999
.long 999
.long 999
.long 999
.long 9999
.long 9999
.long 9999
.long 99999
.long 99999
.long 99999
.long 999999
.long 999999
.long 999999
.long 999999
.long 9999999
.long 9999999
.long 9999999
.long 99999999
.long 99999999
.long 99999999
.long 999999999
.long 999999999
L_TABLE:
.byte 0 ; 0
.byte 1 ; 1
.byte 1 ; 2
.byte 1 ; 3
.byte 1 ; 4
.byte 1 ; 5
.byte 1 ; 6
.byte 2 ; 7
.byte 2 ; 8
.byte 2 ; 9
.byte 3 ; 10
.byte 3 ; 11
.byte 3 ; 12
.byte 3 ; 13
.byte 4 ; 14
.byte 4 ; 15
.byte 4 ; 16
.byte 5 ; 17
.byte 5 ; 18
.byte 5 ; 19
.byte 6 ; 20
.byte 6 ; 21
.byte 6 ; 22
.byte 6 ; 23
.byte 7 ; 24
.byte 7 ; 25
.byte 7 ; 26
.byte 8 ; 27
.byte 8 ; 28
.byte 8 ; 29
.byte 9 ; 30
.byte 9 ; 31
.end
|
| 561.11 | Palindromic HLL | TOOK::APPELLOF | Carl J. Appellof | Tue Aug 12 1986 10:11 | 3 |
| Come on, Bevin, how about giving it to us in the HLL to end all
HLLs: ADA?
|