Den tisdag 7 april 2015 kl. 18:34:32 UTC+2 skrev Dave Angel:
> 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
So you can tell me the first (higest) digit of the integer
2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490
Using base 429496729?
How long time did it take to find it?
--
https://mail.python.org/mailman/listinfo/python-list
