On 04/07/2015 11:40 AM, jonas.thornv...@gmail.com wrote:
Den tisdag 7 april 2015 kl. 16:32:56 UTC+2 skrev Ian:
On Tue, Apr 7, 2015 at 3:44 AM, <jonas.thornv...@gmail.com> wrote:
I want todo faster baseconversion for very big bases like base 1 000 000, so
instead of adding up digits i search it.
I need the fastest algorithm to find the relation to a decimal number.
Digmult is an instance of base at a digitplace (base^x) what i try to find is
the digit for the below condition is true and the loop break.
*********************************
for (digit=0;digit<=base;digit++) {
if((digit+1)*digmult>decNumber)break;
}
*********************************
<snip>
One could start at half base searching, but then i Think i've read that using
1/3 closing in faster?
Do you mean binary search? That would be an improvement over the
linear search algorithm you've shown. Whether a trinary search might
be faster would depend on the distribution of the numbers you expect.
If they're evenly distributed, it will be slower.
I Think also i remember that if the search space so big that at least 22 or 23
guesses, needed.A random Oracle may even faster?
Just pick up a number and get lucky, is it any truth to that?
On average, a random Oracle with a search space of 1000000 will need
1000000 guesses.
Well of course you use same principles like a binary search setting min and max,
closing in on the digit. In this case the searched numbers > base^exp and
number< base^exp+1.
But since the search is within large bases upto 32-bit space, so base
4294967295 is the biggest allowed. I need to find the nearest less exp in base
for each (lets call them pseudo digits). But as you see there it will take time
to add them up. So better doing a binary search, you know min-max half
(iteration). You can do the same for a random oracle min max within range, and
if the number of tries in general over 22 i think a random oracle do it better
than a binary search.
It was a long time since i did this, but i do know there is a threshold where
searching min max with the oracle will be faster than the binary search.
Once again, there's no point in doing a search, when a simple integer
divide can give you the exact answer. And there's probably no point in
going left to right when right to left would yield a tiny, fast program.
I haven't seen one line of Python from you yet, so perhaps you're just
yanking our chain. I'm not here to optimize Javascript code.
Using only Python 3.4 and builtin functions, this function can be
implemented straightforwardly in 7 lines, assuming number is nonnegative
integer, and base is positive integer. It definitely could be done
smaller, but then the code might be more confusing.
--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list
