Mark Dickinson added the comment:
Ah,
https://math.mit.edu/research/highschool/primes/materials/2019/Gopalakrishna.pdf
is interesting - they conjecture a bound on the number of iterations required,
and note that under that conjecture the mod can be replaced by a subtraction.
--
Mark Dickinson added the comment:
Thanks, Tim; very interesting. I hadn't seen this factoring algorithm before.
> That wants the _ceiling_ of the square root.
Looks like what it actually wants is the ceiling analog of isqrtrem: that is,
it needs both the ceiling of the square root *and* the
Tim Peters added the comment:
I've been keeping my eyes open. The only mariginally relevant thing I've
noticed is Hart's "one line factoring" method:
http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf
That wants the _ceiling_ of the square root. And in another place it wants
Tim Peters added the comment:
> Is
>
> i, rem = isqrt_rem(n)
> i + (rem != 0)
>
> better than
>
> (isqrt(n<<2) + 1) >> 1
>
> or
>
> n and isqrt(n-1) + 1
>
> ?
Define "better"? The first way is by far the most obvious of the three, and the
second way the least obvious. The first way
Serhiy Storchaka added the comment:
Is
i, rem = isqrt_rem(n)
i + (rem != 0)
better than
(isqrt(n<<2) + 1) >> 1
or
n and isqrt(n-1) + 1
?
As for use cases, there were few cases in my experience when I needed the
ceiling square root, mostly in simple experiments in REPL, but
Tim Peters added the comment:
I've made several good-faith efforts to find any hint of demand for rounded
isqrt on the web; I've found no direct support for it in other
languages/environments(*); and the one use case you presented isn't compelling.
Building static tables to help implement
Raymond Hettinger added the comment:
> divmod() allows easy emulation of any division rounding mode
It could be used that way, but generally isn't.
Please consider my original request. Adding a keyword argument is easy, clear,
and has almost no mental overhead.
It reads very well in
Case Van Horsen added the comment:
FWIW, gmpy2 uses isqrt_rem. Of course, gmpy2 uses underscores a lot. And uses
next_toward instead of nextafter, and copy_sign instead of copysign, and is_nan
instead of isnan... :(
I would keep the math module consistent and use isqrtrem.
I'll look at
Tim Peters added the comment:
The name "isqrtrem" works fine for me too, and, indeed, is even more
reminiscent of mpz's workalike function.
> the number of times I've needed rounded integer square root
> is small compared with the number of times I've needed rounded
> integer division
Mark Dickinson added the comment:
> Mark didn't mention his use case for rounded isqrt
Mainly for emulation of floating-point sqrt. But the number of times I've
needed rounded integer square root is small compared with the number of times
I've needed rounded integer division.
--
Mark Dickinson added the comment:
A new function isqrt_rem seems like a reasonably natural addition. (Though I'd
call it "isqrtrem", partly by analogy with "divmod", and partly because the
math module isn't very good at doing underscores.)
--
___
Tim Peters added the comment:
Suppose we added isqrt_rem(n), returning the integer pair (i, rem) such that
n == i**2 + rem
0 <= rem <= 2*i
Then:
- Want the floor of sqrt(n)? i.
- The ceiling? i + (rem != 0).
- Rounded? i + (rem > i).
- Is n a perfect square? not rem.
That's how mpz
Tim Peters added the comment:
I'm not rejecting anything. Mark wrote the function, and I'll defer to him.
Yes, you added `initial` to `accumulate()`, and I spent hours in all explaining
to you why it was an utterly natural addition, conspicuous by absence,
including writing up several
Raymond Hettinger added the comment:
So, are you going to reject my feature request? I don't understand why. Both
Mark and I have had valid use cases. The implementation is straight-forward
and simple. The workaround is slow and non-obvious. The default remains the
same so that
Tim Peters added the comment:
Pretend this were the itertools module and you were responding to someone
suggesting a new optional argument to one of its functions. You have tons of
experience rejecting those, and much the same arguments apply, from "not every
one-line function needs to be
Raymond Hettinger added the comment:
> I'd similarly prefer to see recipes in the docs.
Can you elaborate on why you prefer having this in the docs rather than as
built-in functionality?
For me, the rounded case would be the most common. I don't think I'm
better-off writing a wrapper with
Tim Peters added the comment:
[Mark]
> The idea is no more than: "compute an extra bit, then use
> that extra bit to determine which way to round".
Thanks! Despite that this is what the derivation I sketched boiled down to, I
was still missing how general the underlying principle was. Duh!
Mark Dickinson added the comment:
> I'd be happy to see recipes added to the docs for rounded and ceiling flavors
> of isqrt, but am dubious about the value of building them in.
I'd similarly prefer to see recipes in the docs. We already have such a recipe
for ceil(√n).
--
Mark Dickinson added the comment:
> did you invent this?
The idea is no more than: "compute an extra bit, then use that extra bit to
determine which way to round". More generally, for any real number x, the
nearest integer to x (rounding ties towards +infinity) is `⌊(⌊2x⌋ + 1) / 2⌋`.
Now
Tim Peters added the comment:
All cool. Since I doubt these new rounding modes will get much use anyway, it's
not worth arguing about. If I were to do this for myself, the rounding argument
would be one of the three values {-1, 0, +1}, which are already more than good
enough as mnemonics
Raymond Hettinger added the comment:
> So use decimal's ROUND_CEILING, ROUND_FLOOR, and ROUND_HALF_EVEN
It think is would suck to have to type those out. Sorry, I think you're headed
down the path of foolish consistency with an unrelated module and a more
complicated topic. What's wrong
Tim Peters added the comment:
FYI, I had a simpler derivation in mind. Say
sqrt(n) = r + f
where r = isqrt(n) and 0 <= f < 1. Then
sqrt(4n) = 2 * sqrt(n) = 2*(r + f) = 2r + 2f, with 0 <= 2f < 2.
If f < 0.5, 2f < 1, so isqrt(4n) = 2r, and we shouldn't round r up either.
If f > 0.5, 2f > 1,
Tim Peters added the comment:
>> can we use the decimal module's names for the supported
>> rounding modes?
> I'm not sure those make sense because we never get to
> exactly half. There is only floor, ceil, and round,
> not half_up, half_even, etc.
So use decimal's ROUND_CEILING,
Raymond Hettinger added the comment:
> Sweet! New one on me
Tim already knows this but for the record the derivation is isn't tricky.
With y=isqrt(x), then next root is at y+1 and the half way point is y+1/2 which
isn't an integer. The corresponding squares are y**2, (y+1/2)**2, and
Tim Peters added the comment:
[Mark]
> def risqrt(n):
>return (isqrt(n<<2) + 1) >> 1
Sweet! New one on me - did you invent this? It's slick :-)
I'd be happy to see recipes added to the docs for rounded and ceiling flavors
of isqrt, but am dubious about the value of building them in.
If
Mark Dickinson added the comment:
FWIW, when this need has turned up for me (which it has, a couple of times),
I've used this:
def risqrt(n):
return (isqrt(n<<2) + 1) >> 1
But I'll admit that that's a bit non-obvious.
--
___
Python tracker
New submission from Raymond Hettinger :
By default, isqrt(n) gives the floor of the exact square of n. It would be
nice to have a flag to give a rounded result:
y = isqrt(n, round=True)
Alternatively, set a mode argument to one of {'floor', 'round', 'ceil'}:
y = isqrt(n,
27 matches
Mail list logo
