Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Discussion / Faster way to find a digit?

Author
Message
Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 9th Nov 2009 05:06
Is there a faster way to get a single digit from an integer? Here's what I got so far, I only need a 3 digit value, maybe 4 in the long run but not now.

Kevin Picone
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 9th Nov 2009 05:23 Edited at: 9th Nov 2009 05:24
If you really need to do such operations millions of times, then you remove some of the 'static' operations from the inside the loops and pre-solve them..

So this..


could be expressed as





What are you going to be doing with this ?

Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 9th Nov 2009 05:47 Edited at: 9th Nov 2009 05:48
Well I need it for a Radix Sort I'm working on. It works but the way I'm doing it is a bit slow.
Phaelax
DBPro Master
20
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 9th Nov 2009 07:41
Underware Design has DB code demonstrating a Radix sort. I looked into it myself a few years ago when he pointed me to his site.

http://underwaredesign.com/prod_detail.php?rnd=692732119&id=20

demons breath
20
Years of Service
User Offline
Joined: 4th Oct 2003
Location: Surrey, UK
Posted: 9th Nov 2009 11:52 Edited at: 9th Nov 2009 11:56
I'm not sure how fast or efficient it would be, but you could convert it into a string and then choose the character you wanted and then convert this back into an integer.

EDIT: also Kevin I think he wants (n/10)*10 not n/(10*10). So if n was 82:
(n/10)*10=8.2(rounded to 8)*10=80
n/(10*10)=0.82, shortened to 0

"The fools may crash down upon us in thunderous waves, but we shall Jeku slap them back from whence they came"
-BiggAdd Oct 28th 2009
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 9th Nov 2009 14:04
strings are surely faster, especially as you're using integers and there's no decimal point to worry about.

Is there a way to get the decimal places without having to search the string for a point? I can't remember how floats are stored in binary.

"With games, we create these elaborate worlds in our minds, and the computer is there to do the bookkeeping." - Will Wright
Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 9th Nov 2009 15:03
Strings are the slowest way to go. The string statements are just slow as it converts back and forth. If you pop it into my test it shows.


@Phaelax
Thanks for posting that link!


@Kevin Picone
OMG sorting with Hex instead of Dec! Your way is surely faster as bitwise operations are faster and it covers more digits with fewer iterations as well.


Thanks everyone.
Kevin Picone
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 9th Nov 2009 15:29 Edited at: 9th Nov 2009 15:31
demons breath:


Quote: " EDIT: also Kevin I think he wants (n/10)*10 not n/(10*10). So if n was 82:
(n/10)*10=8.2(rounded to 8)*10=80
n/(10*10)=0.82, shortened to 0
"


Nah, the divisions will be cast as integer divisions, not floating point in this case. So 82/10 in DB & DBpro ='s 8


Ashingda 27:

ahh, a Radix sort. Now i understand why you're timing it the separation.

In the version linked above, I've used 4bit nibbles (base2) rather than base 10. The only reason (from memory) was to make accessing the 'digits' easier. Ie. digit = (Number / BitShiftOffset ) and BitMask

If the range your data is only 3 digit base 10 (0 to 999) (approximately 10 bit in base 2). You could trying split it into two passes of 5bit sweeps. But nibbles is possibly the best option, but you get more passes..

demons breath
20
Years of Service
User Offline
Joined: 4th Oct 2003
Location: Surrey, UK
Posted: 9th Nov 2009 19:24
Quote: "Nah, the divisions will be cast as integer divisions, not floating point in this case. So 82/10 in DB & DBpro ='s 8"


I know but they'll come out with different answers


It's to do with the order of operation. Basically, if you imagine it's a fraction, his method multiplies the numerator, whereas yours multiplies the denominator, therefore coming out with completely different numbers.

"The fools may crash down upon us in thunderous waves, but we shall Jeku slap them back from whence they came"
-BiggAdd Oct 28th 2009
BN2 Productions
20
Years of Service
User Offline
Joined: 22nd Jan 2004
Location:
Posted: 9th Nov 2009 21:06
I would suggest a mixture of strings and variables. Variables can be used to determine if it is an integer or not (and how many decimal places it is)

Great Quote:
"Time...LINE??? Time isn't made out of lines...it is made out of circles. That is why clocks are round!" -Caboose
ionstream
19
Years of Service
User Offline
Joined: 4th Jul 2004
Location: Overweb
Posted: 10th Nov 2009 11:39
Well this is a bit on the difficult side, but if you wanted to do it in base 16 (or 8 i guess) then there are a lot of optimizations you can do. So if you wanted to get the digits in base 16:

number = 0x12345;

digit1 = number & 0xF;
number = number >> 4; // shift it over 4 bits so that the next digit is first

digit2 = number & 0xF;
number = number >> 4;

And so forth. I guess this was what Kevin Picone was explaining, and its a whole lot faster than dividing.

Van B
Moderator
21
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 10th Nov 2009 15:21
Just to add...

A little idea for finding the position of the decimal point...

So A is a long number

A$=str$(a)
Al=len(A$)
DP_l$=left$(A$,len(str$(int(A))))
DP_r$=right$(A$,Al-1-len(DP_l$))

And the above should hopefully split it into 2 halves, DP_l$ before the dec point and DP_r$ after it. This just uses the length of the string of the integer to find the spot - more directly, the dec point could be returned with len(str$(int(A)))+1.


Health, Ammo, and bacon and eggs!
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 10th Nov 2009 15:26
@VanB
clever

"With games, we create these elaborate worlds in our minds, and the computer is there to do the bookkeeping." - Will Wright
Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 10th Nov 2009 17:26
Strings are slow and the function I need to use this for is executed continuously at about 500 iterations per loop.

The whole idea of looping 1000000 times in this code is just to test it's speed along with other methods.

Login to post a reply

Server time is: 2024-03-29 14:10:15
Your offset time is: 2024-03-29 14:10:15