[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.javascript

Time complexity and division

JT

6/20/2015 11:21:00 AM

Does anyone know the time complexity of my suggested min max search operation vs a schoolbook long division, sieve of Erathostenes or Karatsuba?

Is there any other name for it than min max search?

10 Answers

Scott Sauyet

6/21/2015 1:09:00 AM

0

jonas.thornvall@gmail.com wrote:
> Does anyone know the time complexity of my suggested min max search operation
> vs a schoolbook long division, sieve of Erathostenes or Karatsuba?

Yes.

> Is there any other name for it than min max search?

Yes.


-- Scott

P.S. Have you learned yet how USENET works?

JT

6/21/2015 7:24:00 AM

0

Den söndag 21 juni 2015 kl. 03:08:43 UTC+2 skrev Scott Sauyet:
> jonas.thornvall@gmail.com wrote:
> > Does anyone know the time complexity of my suggested min max search operation
> > vs a schoolbook long division, sieve of Erathostenes or Karatsuba?
>
> Yes.
>
> > Is there any other name for it than min max search?
>
> Yes.
>
>
> -- Scott
>
> P.S. Have you learned yet how USENET works?

No

JT

6/21/2015 8:02:00 AM

0

Den söndag 21 juni 2015 kl. 03:08:43 UTC+2 skrev Scott Sauyet:
> jonas.thornvall@gmail.com wrote:
> > Does anyone know the time complexity of my suggested min max search operation
> > vs a schoolbook long division, sieve of Erathostenes or Karatsuba?
>
> Yes.
>
> > Is there any other name for it than min max search?
>
> Yes.
>
>
> -- Scott
>
> P.S. Have you learned yet how USENET works?

Of course the best case for a min max search is that we find the digit multiple it first try so "1" comparisson, and the worst must be that we need sqrt(n) comparissons.

And within the average case the multiple would be found after sqrt(n)/2 comparissons?

Since it can be used not only as a base changin algorithm, but easily can be modified into doing division. One wonder how it compairs doing division.
So it seem the time complexity is dependent upon the base used in this algorithm.

But i guess the time complexity also must take into account not only the min and max comparissons but also the multipliations and digit comparissons needed,
to really find min and max?

So can one state that a comparissons in itself is one operation, that does not seem fair it is easier to find and set min and max for small numbers than for real big ones.

Evertjan.

6/21/2015 8:10:00 AM

0

jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:

>> P.S. Have you learned yet how USENET works?
>
> Of course the best case for ......

As Usenet is a platform of discussion-lists,
you should bring in argumentation for your statements.

Your 'of course' just means:
'I trust you fall for my unforgivable lack of argumentation'.

And please stop responding to yourself and answering yourself,
Usenet is not a platform for monologues.

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

JT

6/21/2015 9:49:00 AM

0

Den söndag 21 juni 2015 kl. 10:09:55 UTC+2 skrev Evertjan.:
> jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:
>
> >> P.S. Have you learned yet how USENET works?
> >
> > Of course the best case for ......
>
> As Usenet is a platform of discussion-lists,
> you should bring in argumentation for your statements.
>
> Your 'of course' just means:
> 'I trust you fall for my unforgivable lack of argumentation'.
>
> And please stop responding to yourself and answering yourself,
> Usenet is not a platform for monologues.
>
> --
> Evertjan.
> The Netherlands.
> (Please change the x'es to dots in my emailaddress)
Well i must say i find it hard to calculate the time complexity, especially since the base used seem to matter.

The weight of the operands seem to be vital, and really should be taken into account when doing comparissons.

If i have an algorithm performing division by a min max search, i am a bit lost about what really is the timecomplexity. Because there is numerous different operations performed. If one take the actual min max search for a digit, it follows naturally that the weight of digit is dependent upon the base.

So the higher the base the less total operations is performed doing the divisions. There is a number of operations performed to do the division, but which one is the actual time complexity.

1. Search and store the multiples for base x -> x^1,x^2,x^3... and so on.
Loop until number exhausted or specified precision reached.
Loop until multiple found
2. Use the min max search and find the polynomial multiplier for digit y*x^z
3. Compare the result of the multiplication with the number.
End.
4. Subtract the product from the number.
End.

I have a hard time to conclude what the actual time complexity is when using this algorithm doing division and it also seem dependent upon the size of base x.

JT

6/21/2015 10:02:00 AM

0

Den söndag 21 juni 2015 kl. 11:48:38 UTC+2 skrev jonas.t...@gmail.com:
> Den söndag 21 juni 2015 kl. 10:09:55 UTC+2 skrev Evertjan.:
> > jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:
> >
> > >> P.S. Have you learned yet how USENET works?
> > >
> > > Of course the best case for ......
> >
> > As Usenet is a platform of discussion-lists,
> > you should bring in argumentation for your statements.
> >
> > Your 'of course' just means:
> > 'I trust you fall for my unforgivable lack of argumentation'.
> >
> > And please stop responding to yourself and answering yourself,
> > Usenet is not a platform for monologues.
> >
> > --
> > Evertjan.
> > The Netherlands.
> > (Please change the x'es to dots in my emailaddress)
> Well i must say i find it hard to calculate the time complexity, especially since the base used seem to matter.
>
> The weight of the operands seem to be vital, and really should be taken into account when doing comparissons.
>
> If i have an algorithm performing division by a min max search, i am a bit lost about what really is the timecomplexity. Because there is numerous different operations performed. If one take the actual min max search for a digit, it follows naturally that the weight of digit is dependent upon the base.
>
> So the higher the base the less total operations is performed doing the divisions. There is a number of operations performed to do the division, but which one is the actual time complexity.
>
> 1. Search and store the multiples for base x -> x^1,x^2,x^3... and so on.
> Loop until number exhausted or specified precision reached.
> Loop until multiple found
> 2. Use the min max search and find the polynomial multiplier for digit y*x^z
> 3. Compare the result of the multiplication with the number.
> End.
> 4. Subtract the product from the number.
> End.
>
> I have a hard time to conclude what the actual time complexity is when using this algorithm doing division and it also seem dependent upon the size of base x.

I have a hard time to imagine that the actual time complexity is only the actual min max search finding the digits.

Because they will be miles apart if you chose to do it in base 2 or if you chose to use the sqrt(divisor) as base.

Ben Bacarisse

6/21/2015 11:36:00 AM

0

jonas.thornvall@gmail.com writes:

> Does anyone know the time complexity of my suggested min max search
> operation vs a schoolbook long division, sieve of Erathostenes or
> Karatsuba?

I don't know what your "min max search operation" is and I'm puzzled by
the fact you want to compare is with three apparently different things
(a division algorithm, a mother of finding primes and a multiplication
algorithm).

> Is there any other name for it than min max search?

I *think* it's what everyone else calls a binary search, but you don't
show it so that's just guessing.

--
Ben.

Evertjan.

6/21/2015 7:44:00 PM

0

jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:

> Den s?ndag 21 juni 2015 kl. 10:09:55 UTC+2 skrev Evertjan.:
>> jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:
>>
>> >> P.S. Have you learned yet how USENET works?
>> >
>> > Of course the best case for ......
>>
>> As Usenet is a platform of discussion-lists,
>> you should bring in argumentation for your statements.
>>
>> Your 'of course' just means:
>> 'I trust you fall for my unforgivable lack of argumentation'.
>>
>> And please stop responding to yourself and answering yourself,
>> Usenet is not a platform for monologues.

> Well i must say i find it hard to calculate the time complexity,
> especially since the base used seem to matter.

And here again you do not respond to the posting,
but just go on doing monologues.

Do you do that in real life too?

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

Evertjan.

6/21/2015 8:02:00 PM

0

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote on 21 Jun 2015 in
comp.lang.javascript:

> jonas.thornvall@gmail.com writes:
>
>> Does anyone know the time complexity of my suggested min max search
>> operation vs a schoolbook long division, sieve of Erathostenes or
>> Karatsuba?
>
> I don't know what your "min max search operation" is and I'm puzzled by
> the fact you want to compare is with three apparently different things
> (a division algorithm, a mother of finding primes and a multiplication
> algorithm).
>
>> Is there any other name for it than min max search?
>
> I *think* it's what everyone else calls a binary search, but you don't
> show it so that's just guessing.

I remember this had to do with "alpha-beta pruning" in chess-programming.

Ah yes, here it is:

"Alpha?beta pruning is a search algorithm that seeks to decrease the number
of nodes that are evaluated by the minimax algorithm in its search tree."
[Allen Newell and Herbert A. Simon, 1958].
<https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_p...

"A minimax approximation algorithm [..] is a method to find an approximation
of a mathematical function that minimizes maximum error."
<https://en.wikipedia.org/wiki/Minimax_approximation_alg...

Deep Alpha-Beta Pruning: An alpha or beta cut-off value may be used to prune
trees at any node which is an even number of levels below it
[Alpha-beta Pruning Algorithm, Fuller, Gaschnig and Gillogly, 1973]

========================

Odd that an odd number of levels was even disregarded,
perhaps as it would give a unacceptable bias?

Indeed this may have been decisive in combatting the time complexity
of the primitive calculating machines used during that computer stone-age.

Perhaps Jonas was still inside the whale at that time?

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

Richard Damon

8/15/2015 3:02:00 PM

0

On 6/21/15 4:01 PM, Evertjan. wrote:
> Ah yes, here it is:
>
> "Alpha?beta pruning is a search algorithm that seeks to decrease the number
> of nodes that are evaluated by the minimax algorithm in its search tree."
> [Allen Newell and Herbert A. Simon, 1958].
> <https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_p...
>
> "A minimax approximation algorithm [..] is a method to find an approximation
> of a mathematical function that minimizes maximum error."
> <https://en.wikipedia.org/wiki/Minimax_approximation_alg...
>
> Deep Alpha-Beta Pruning: An alpha or beta cut-off value may be used to prune
> trees at any node which is an even number of levels below it
> [Alpha-beta Pruning Algorithm, Fuller, Gaschnig and Gillogly, 1973]
>
> ========================
>
> Odd that an odd number of levels was even disregarded,
> perhaps as it would give a unacceptable bias?
>
> Indeed this may have been decisive in combatting the time complexity
> of the primitive calculating machines used during that computer stone-age.
>
> Perhaps Jonas was still inside the whale at that time?
>

I think the even number of layers is due to the fact that even layers
and odd layers are acting different. For example, even layers may be
maximizing, while the odd layers are minimizing, or even layers are my
choices, odd layers are my opponents.

If I currently have a value of X and I am the maximizer, then if some
odd layer below currently can say no higher than Y, less than X, then I
can prune all the unevaluated even nodes just below that layer, as I
know that I will chose a path that avoids this node, since I know I can
do better. (I can't 'prune' the node that said Y, as I have already
started to evaluate it, the best I can do is prune everything
unevaluated just below it and thus finish the evaluation of that node. I
don't get the real answer for that node, but I know that the even node
above it either has a better option to take, or some higher even node
has a better option and I won't get to here).

An alternative description would be that we can prune off (and abort the
calculation of) any odd branch that we know we won't enter as we have
better choices. In that model WE can't prune even branches as those are
based on our opponents move, those will get pruned when we flip our
brain and start to think of what they should do for each of the
positions we are thinking of giving them. THEY will prune off the even
branches. Mathematically, it seems preferred to described the nodes
pruned as those never evaluated, as opposed to those whose evaluations
are not completed.

Similar logic to prune out an odd layer would look at the value of the
even layer above it and compare that to some odd layer above it. But, we
do the pruning based on a node, and that node it the base, which is
called level 0 (or even), so an pruning can't occur there (it might
happen when we recurse, and effectively swap the definition of even and
odd layers are reverse the value function).