Re: Finding minimum in arithmetic series modulo N
- From: Tim Little <tim@xxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Fri, 11 Apr 2008 00:29:47 -0500
On 2008-04-10, 3130@xxxxxxxx <3130@xxxxxxxx> wrote:
x(k) = (A + kD) mod N[...]
k takes values 0, 1, 2 ... M-1.[ Find minimum x(k) ]
I'm guessing you mean the ordering in which n-1 < n for n != 0 mod N.
Yes, there certainly are methods of search that are much better than
brute force. Think of where the successive values of the sequence
"land".
You start at A and increment by D, eventually exceeding N and wrapping
around to some value m1 < D at k = k1. If k1 >= M then A is the
smallest value.
Now consider only every floor(N/D) iterations from then on. Obviously
none of the intermediate values can be a minimum. Successive values
in this sequence increase by some amount r < D. If r > 0 you can now
reduce the problem to be that of finding the minimum value of
x'(k') = (m1 + k' r) mod D, for 0 <= k' < M / floor(N/D).
- Tim
.
- Prev by Date: Re: Cubic spline path (was: rotation in 3D)
- Next by Date: math -- values of f(x) (mod p)
- Previous by thread: Re: Finding minimum in arithmetic series modulo N
- Next by thread: Re: Finding minimum in arithmetic series modulo N
- Index(es):
Relevant Pages
|
