How can I modulo when my numbers start from 1, not zero?

Question

I guess the solution for this is quite simple, but I've been thinking about it for a while and couldn't come up with an elegant solution.

I have a range of numbers, e.g. 1..10 = (1,2,3,4,5,6,7,8,9,10), which is circular, meaning the number after the last one is again the first one (next(10)=1).

For a given number i>0 in the range, I would like to calculate the next m-th, and previous m-th number. e.g. next(5,1)=6 next(10,1)=1 next(10,2)=2 prev(5,2)=3 prev(1,1)=10 prev(1,2)=9.

For next I can just take (i+m)%n where n is the length of the range (n=10 in the example). But for prev I couldn't find an elegant solution.

Answer 1

Your next = (i + m) % n isn't right anyway - it'll return zero in some cases.

Try this instead:

next(i, m) = ((i - 1) + m) % n + 1
prev(i, m) = ((i - 1) + n - m) % n + 1

In effect, take one off, then find the correct value, and then add the one back on again.

For prev, add n first to ensure that you never take the modulo of a negative number

Answer 2

Just subtract 1 and add 1 afterwards.

In most programming languages, you need to watch out when finding a "previous" value, because for negative numbers, modulo does not work as you want in this case: it returns a negative number.

Here's the C/C++ version:

int next(int i, int m, int n) { return (i + m - 1) % n + 1; }
int prev(int i, int m, int n) { return (i - m + n - 1) % n + 1; }

However, in Perl modulo always returns a positive value (at least when the second operand is a positive integer). Basically it does what you want. So you can write the following and leave out the + $_[2]:

sub nxt { ($_[0] + $_[1] - 1) % $_[2] + 1; }
sub prv { ($_[0] - $_[1] - 1) % $_[2] + 1; }

Answer 3

What is difference between next(i,m) and previous(i,-m)? Nothing!. So let's go (i - 1 + n + m % n) % n + 1:

$ perl -le 'sub gen {my $n = shift; return sub{ my ($i, $m) = @_; return ($i - 1 + $n + $m % $n) % $n + 1;};} $"=","; for my $n (2..5) { my $f = gen($n); print "$n: @{[map {$f->(1,$_)} -10 .. 10]}"}'
2: 1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1
3: 3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2
4: 3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3
5: 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1

Answer 4

Hello,

A few words in general first, if you don't mind.

Your confusion in implementing a "prev" function comes from thinking about this problem in domains of positive and negative integers. Think about it in terms of geometry, if you visualized a circle with 10 equally spaced points then solution looks like this :

As you correctly specified, given a range [x..z], where range is circular, you can find the next m-th number as (i+m)%k where i belongs to [x..z] and k is the length of the range.

Now, for the "previous" m-th member. The previous number can be found by calculating (or more visually expressed, "arriving at") the previous m-th number position like this (pseudocode) :

prev(m, i) = (i + len(range) - m) % len(range)

For example, if you take the previous first of number 10 , then

prev(1,10) = (10+10-1)%10 = 19%10 = 9

Previous 3rd for number 5 = prev(3,5) = (5+10-3)%10 = 12%10 = 2 . Etcetera, etcetera. Very simple, and elegant, huh?

The only caveat here is that if i == m , the modulo will be a zero, so you need a handling mechanism for this result in both the next() and prev() functions.

Hope this helps, Jas.

Answer 5

You might look at the source to Tie::Cycle, a module I created to cycle through arbitrary lists.

Remember that numbers are really just glyphs that stand in for something. If you have a Perl list of these glyphs, you still have a sequence starting at zero because you do the math on the list indices, not the glyphs. When you've selected the right list index, you use the element at that index.

If you want very large lists or lazy lists, you can still do this, but you just have to do a bit more work.