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.

Hanford

This isn't specific to Perl in any way. I would suggest looking for a better tag. – Annabellannabella

Tags changed from perl to modulo based on question's actual content. – Honduras

Answer 1

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; }

Mafia

If the number will be non-negative, and there's no danger of numerical overflows, I prefer to add (base-1) rather than subtracting one. – Idempotent

A good treatment of the different implementations of the modulo "operator" from a mathematical viewpoint: mathforum.org/library/drmath/view/52343.html . Actually, the % operator is not defined in C/C++ for negative arguments, but most implementations follow the IEEE 754 standard, which is the same as Ada's REM operator. Perl's % implements the same thing as Ada's MOD operator. – Mafia

@gpvos: Careful about the difference between undefined and implementation-defined behavior. % on negative numbers in C++03 is the latter. – Lodestone

Nice @gpvos. I used your C example to cycle through hit of hits in a search result in javascript. next is hooked up to cycle(1) and prev to cycle(-1), where cycle is cycle (direction) { this.hit = (direction === -1 ? this.hit + direction + this.hits - 1 : this.hit + direction - 1) % this.hits + 1 } – Nightstick

The link from my earlier comment is dead; archive link: web.archive.org/web/20201212003443/http://mathforum.org/library/… – Mafia

Answer 2

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

Nicks

I really like this answer best (+1). And the description of "take one off, find the correct value, then add the one back" makes the one liner super intuitive, as well as nice and concise. – Spheno

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

Cooking

Interesting: perl modulo is different from C modulo. #include <stdio.h> void main() { for (int i = -10; i <= 10; ++i) { printf("%d ", i % 5); } } gives: 0 -4 -3 -2 -1 0 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 0 perl -e 'for (-10..10) { printf "%d ", $_ % 5; }' gives: 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 – Mafia

Answer 4

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.

Else

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.

Guarino

Answer 6

I have this solution in R:

pred <- function(n) n - 1L # cf. Pascal's pred
succ <- function(n) n + 1L # cf. Pascal's succ
`%mod1%` <- function(m, n) succ(pred(m) %% n) # modulo from 1
cat(-11:24 %mod1% 12) # test
# 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

Decompose

Answer 7

I found the following one-liner quite elegant for JavaScript and other languages, that can handle 0 as logically false:

const res = val % n || n;

Modulo your value (val) with your divisor (n). When this results in 0, return the divisor instead.

Cloe

Answer 8

Say you want to map from 1 to n not 0 to n-1 eg n=5, range 1 to x, results 0 to 4,0mod5=0 1mod5=1, 2mod5=2... xmod5 results 0 whenever x=5*k. Use ((x-1)mod5)+1, x must be >0. This will always map (count) in 1 to 5 range, instead 0 to 4.

Shanon

Welcome to stack overflow. thank you for contributing. Please make your answer more readable so everyone can enjoy! – Rosemonde