For positive triplet (n,x,y), n/(x*y)==n/x/y even in integer division

More than 1 year has passed since last update.

For positive triplet (n,x,y), n/(x*y)==n/x/y even in integer division.

This should be useful to avoid overflow.

Let's prove this below.


if n.divmod(xy) is (a,b), n can be represented as:

n=axy+b (0<=b<xy)

On the other hand, if n.divmod(x) is (c,d) and c.divmod(y) is (e,f), n can be represented as:

n=cx+d (0<=d<x)

c=ey+f (0<=f<y)
n=x(ey+f)+d=exy+xf+d

Now suppose d is x-1 and f is y-1. Then xf+d becomes x(y-1)+x-1=xy-1 (<xy).

This means 0<=xf+d<xy and a(==n/(x*y))==e(==n/x/y) has been proved.

Also, in n/(x*y), x and y are exchangable. So n/x/y == n/y/x. (Q.E.D.)

検索用:自然数の3つ組(n,x,y)に対してn/(x*y)==n/x/yは整数除算でも常に成立しますので、オーバーフローを避けるのに役立つでしょう。


170513

Actually this lemma is used for icbrt (integer cubic-root) used in http://qiita.com/cielavenir/items/2a685d3080862f2c2c47 .


180127

For fear, I confirmed small case...

#!/usr/bin/ruby

(1..10000).each{|n|
(1..100).each{|x|
(1..100).each{|y|
r0=n/(x*y)
r1=n/x/y
r2=n/y/x
if r0!=r1 || r1!=r2
raise [n,x,y].join(',')
end
}
}
}

https://qiita.com/cielavenir/items/d419b448d1c65eae2868 is another example where this lemma is useful.