Optionally support rounding for math.isqrt()

[rhettinger]

BPO	46187
Nosy	@tim-one, @rhettinger, @mdickinson, @serhiy-storchaka

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/mdickinson'
closed_at = None
created_at = <Date 2021-12-27.19:29:59.437>
labels = ['type-feature', 'library', '3.11']
title = 'Optionally support rounding for math.isqrt()'
updated_at = <Date 2022-02-06.13:23:47.677>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2022-02-06.13:23:47.677>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2021-12-27.19:29:59.437>
creator = 'rhettinger'
dependencies = []
files = []
hgrepos = []
issue_num = 46187
keywords = []
message_count = 27.0
messages = ['409243', '409244', '409264', '409278', '409279', '409281', '409294', '409312', '409361', '409362', '409378', '409395', '409397', '409405', '409406', '409423', '409425', '409426', '409427', '409474', '409523', '409634', '409655', '409689', '412592', '412628', '412631']
nosy_count = 5.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'casevh', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue46187'
versions = ['Python 3.11']

Linked PRs

• gh-90345: Add math.integer.isqrt_rem() #150224

[rhettinger]

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, mode='round')

I would like something better than this:

    def risqrt(x):
        'Big integer version of: round(sqrt(x)).'
        y = isqrt(x)
        s = y ** 2
        return y if x <= s + y else y + 1

    def cisqrt(x):
        'Big integer version of: ceil(sqrt(x)).'
        return isqrt(x - 1) + 1

My use case arose when building a table of square roots incorporated in arbitrary precision functions implemented with scaled integer arithmetic:

    def get_root_table(base, steps, scale):
        s = []
        x = round(base * scale)
        for i in range(steps):
            x = risqrt(x * scale)
            s.append(x)
        return s

[mdickinson]

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.

[tim-one]

[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 they are added via an optional rounding argument, can we use the decimal module's names for the supported rounding modes?

[rhettinger]

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 (y+1)*2. With a multiple of four, those become 4*y**2, 4(y+1/2)**2, and 4*y+1)**2 which are equivalent to the squares of consecutive integers: (2y)**2, (2y+1)**2, and (2y+2)**2. Adding one gives the roots 2y+1, 2y+2, and 2y+3. The floor division eliminates the constant term giving the desired roots y, y+1, and y+1.

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.

[tim-one]

> 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, ROUND_FLOOR, and ROUND_HALF_EVEN. It's irrelevant that the halfway case can't occur: it's still following the ROUND_HALF_EVEN rules, it's just that one of those rules never happens to apply in this context. So what? Your _intent_ is to supply "best possible rounding", and that's what ROUND_HALF_EVEN means. It's not doing any favors to make up a new name for a rounding mode that only applies to values that can never tie. Tail. dog, wag ;-) If someone knows what half/even does, they already know what _this_ rounding mode does. Why complicate it with a useless distinction?

[tim-one]

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, so sqrt(4n) = 2r + 1 + (2f - 1), with 0 <= 2f - 1 < 1, so isqrt(4n) = 2*r + 1. In this case (f > 0.5) we need to round r up.

f = 0.5 can't happen.

Regardless, I don't believe I would have thought of this myself! It was an unexpected delight :-

[rhettinger]

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 with keeping consistent the name of the existing functions: round, floor, and ceil which are self-explanatory and much better known than the decimal module constants. Also, the intent for these to be substitutable for existing code which uses round(sqrt(x)), floor(sqrt(x)), and ceil(sqrt(x)). If those are the starting point, then round, floor, and ceil are a logical progression from the existing code. It is also consistent with how the numeric tower approaches various ways of rounding.