2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-05-11

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.

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?