Some thoughts on integer exponentiation (and an implementation)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Some thoughts on integer exponentiation (and an implementation)

Stefan Ginsberg
For the most part I am pleased with Lua's integer implementation.
I do find it lacking in that it does not support "true" integer exponentiation,
so I made an implementation for my own needs. Sharing it here in case
anyone else finds this useful, patched against Lua 5.3.4:
Available from here: http://lua-users.org/files/wiki_insecure/power_patches/5.3/lua-5.3.4_ipow.patch

In brief, it makes the '^'-operator perform integer exponentiation using (unsigned)
exponentiation by squaring for two integer operands 'b^n' with a non-negative exponent.
Overflow is ignored, and wraps around to give the same result as repeated multiplication would*.
A negative exponent is handled according to 1 of 3 #define-d modes.
These are either raising an error, converting operation to float, or defining the exponentiation as '1 // (b^abs(n))'.

These modes are the main ideas I have seen proposed for how to handle negative 'n'.
I initially favored the "convert to float" solution as the most useful (and most compatible).
However I now consider the "raise an error" solution to be more useful (see below).
I am unsure if anyone actually wanted the idiv-solution but it is included for completeness.

So why would disallowing "10^-3" be more useful?
First of all, it follows the type-not-value-is-what-matters rule, and '10^-3 == 0.001' breaks that.
I want my integer and float math distinct, and with division one can choose between true-or-integer division to get the desired result.
Unless a new operator ('**' anyone?) is made then something has to give.

Moreover, one could claim that this error-behavior already exists in Lua.
Both '1 // 0' and '1 %% 0' will raise errors instead of "promoting" the operation
to float to represent inf or nan, so why should '10^-3' promote to float to represent a fraction?

Also, it makes '^' behave consistent with an "integer-only" setting. Allowing '^'
to work in such a setting was my motivation for implementing this to begin with,
and '10^-3' behaving differently there is less than ideal.

In my view, integer exponentiation shouldn't be too much of a hassle,
if one is just explicit with the type of numbers used: '10.0^-3.0'

Thoughts?

* That is the intention anyway. If someone notices a case where this doesn't hold,
  or some other problem with the algorithm, please let me know!
Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Dirk Laurie-2
2017-05-13 22:16 GMT+02:00 Stefan Ginsberg <[hidden email]>:

> Unless a new operator ('**' anyone?) is made then something has to give.
>
> Moreover, one could claim that this error-behavior already exists in Lua.
> Both '1 // 0' and '1 %% 0' will raise errors instead of "promoting" the
> operation
> to float to represent inf or nan, so why should '10^-3' promote to float to
> represent a fraction?
>
> Also, it makes '^' behave consistent with an "integer-only" setting.
> Allowing '^'
> to work in such a setting was my motivation for implementing this to begin
> with,
> and '10^-3' behaving differently there is less than ideal.
>
> In my view, integer exponentiation shouldn't be too much of a hassle,
> if one is just explicit with the type of numbers used: '10.0^-3.0'
>
> Thoughts?

Well, I raised a question much like this less than a year ago [1].
The usual sort of list discussion followed and the matter was dropped.

What I wanted was that if M and N are integers, and M^N can be
represented exactly, the exponentiation operator should do that.

You're going a step further and say: if it overflows, let it overflow.

I'm trying to think of a plausible use case and can't. If we had unsigned
integers, I could.

[1] http://lua-users.org/lists/lua-l/2016-06/msg00077.html

Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Stefan Ginsberg

On Sun, May 14, 2017 at 7:02 AM, Dirk Laurie <[hidden email]> wrote:

Well, I raised a question much like this less than a year ago [1].
The usual sort of list discussion followed and the matter was dropped.

What I wanted was that if M and N are integers, and M^N can be
represented exactly, the exponentiation operator should do that.

You're going a step further and say: if it overflows, let it overflow.

I'm trying to think of a plausible use case and can't. If we had unsigned
integers, I could.

[1] http://lua-users.org/lists/lua-l/2016-06/msg00077.html


I believe you made a good case for integer exponentiation in that post.

The implementation does not check for overflow simply to be consistent with the other mathematical operators.

I see a problem with rounding instead of wrapping around in that it makes '^' behave differently from '*'.
That is, 'b ^ 3' and 'b * b * b' resulting in both different types and values for different integer 'b'.
If integer '^' checks for overflow then shouldn't '*' do the same? As you point out, '*' is also prone to overflow.

If a rounded float result is desired then why not just use float operands instead of integers?
Me I would rather have a wrapped around integer than a rounded float, if I am using integer operands.
I don't find much use for wrap-around either (in a high-level language) but that's how Lua does it.

Something I would find more useful is if overflowed integer results were returned as nil (i.e. 123^456 == nil).
Not just for '^' but for all relevant integer operations. This would also make unsigned numbers more manageable.
Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Sean Conner
It was thus said that the Great Stefan Ginsberg once stated:
>
> Something I would find more useful is if overflowed integer results were
> returned as nil (i.e. 123^456 == nil).
> Not just for '^' but for all relevant integer operations. This would also
> make unsigned numbers more manageable.

  Such checks add overhead to Lua (but as usual, one would have to test to
see of the overhead is unacceptable).  Unfortunately, there is no cheap way
to check for overflow in C (unlike assembly [1]).

  Second, I'm not sure if I like returning nil.  

        a = 1
        b = 63
        c = 1

        x = (1 << b) + c

        stdin:1: attempt to perform arithmetic on a nil value
        stack traceback:
                stdin:1: in main chunk
                [C]: in ?
>
  Okay, that doesn't happen now---what happens now is that x =
9223372036854775807 instead of -9223372036854775809 because of rollover.
I can see an argument for it, but ...

  -spc (but I'm not sure if I want to see how sloppy I've been with math ... )

[1] http://boston.conman.org/2015/09/07.1

        It's not much overhead in time, but it does increase the memory
        usage of the code because of the overhead of checking for overflow.

Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Stefan Ginsberg

> On 14 May 2017, at 23:46, Sean Conner <[hidden email]> wrote:
>
> It was thus said that the Great Stefan Ginsberg once stated:
>>
>> Something I would find more useful is if overflowed integer results were
>> returned as nil (i.e. 123^456 == nil).
>> Not just for '^' but for all relevant integer operations. This would also
>> make unsigned numbers more manageable.
>
>  Such checks add overhead to Lua (but as usual, one would have to test to
> see of the overhead is unacceptable).  Unfortunately, there is no cheap way
> to check for overflow in C (unlike assembly [1]).
>
>  Second, I'm not sure if I like returning nil.  
>
>    a = 1
>    b = 63
>    c = 1
>
>    x = (1 << b) + c
>
>    stdin:1: attempt to perform arithmetic on a nil value
>    stack traceback:
>            stdin:1: in main chunk
>            [C]: in ?
>>
>  Okay, that doesn't happen now---what happens now is that x =
> 9223372036854775807 instead of -9223372036854775809 because of rollover.
> I can see an argument for it, but ...
>
>  -spc (but I'm not sure if I want to see how sloppy I've been with math ... )
>
> [1]    http://boston.conman.org/2015/09/07.1
>
>    It's not much overhead in time, but it does increase the memory
>    usage of the code because of the overhead of checking for overflow.
>

To be clear that idea is only for the affected mathematical operators, not bitwise shifts.

I don't consider shifting out bits the same thing as overflow, it is another type of operation.

While checked integer math would incur some overhead, compared to something like a call,
table indexing, or even the overhead for doing the operation itself I believe it would be negligible.

For example, checked add:
'if ((ib ^ ic) >= 0 && (ib ^ ia) < 0)'
Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Sean Conner
It was thus said that the Great Stefan Ginsberg once stated:

>
> > On 14 May 2017, at 23:46, Sean Conner <[hidden email]> wrote:
> >
> >  Second, I'm not sure if I like returning nil.  
> >
> >    a = 1
> >    b = 63
> >    c = 1
> >
> >    x = (1 << b) + c
> >
> >    stdin:1: attempt to perform arithmetic on a nil value
> >    stack traceback:
> >            stdin:1: in main chunk
> >            [C]: in ?
> >>
> >  Okay, that doesn't happen now---what happens now is that x =
> > 9223372036854775807 instead of -9223372036854775809 because of rollover.
> > I can see an argument for it, but ...
> >
> To be clear that idea is only for the affected mathematical operators, not
> bitwise shifts.
>
> I don't consider shifting out bits the same thing as overflow, it is
> another type of operation.

  Shifting is just multiplication or division by two.  At the CPU level,
there is a distinction made between shifts (left (multiplication) which
shifts in 0s and right (division) which shifts in the sign bit) and rotates
(shifts the bits, rotating in the carry bit).

  -spc


Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Stefan Ginsberg

> On 15 May 2017, at 01:13, Sean Conner <[hidden email]> wrote:
>
> Shifting is just multiplication or division by two.  At the CPU level,
> there is a distinction made between shifts (left (multiplication) which
> shifts in 0s and right (division) which shifts in the sign bit) and rotates
> (shifts the bits, rotating in the carry bit).
>
> -spc

What I really meant is that a shift operator which disallows shifting out (all) bits would be less-than-useful.



Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Sean Conner
It was thus said that the Great Stefan Ginsberg once stated:

>
> > On 15 May 2017, at 01:13, Sean Conner <[hidden email]> wrote:
> >
> > Shifting is just multiplication or division by two.  At the CPU level,
> > there is a distinction made between shifts (left (multiplication) which
> > shifts in 0s and right (division) which shifts in the sign bit) and rotates
> > (shifts the bits, rotating in the carry bit).
> >
> > -spc
>
> What I really meant is that a shift operator which disallows shifting out
> (all) bits would be less-than-useful.

  I'm still confused.  Ignoring rotates (which rotate the bits) CPUs tend to
support two forms of shifting, an unsigned variant (where 0 is copied in for
right shifts) and a signed variant (where the sign bit is copied for right
shifts) and are (nominally) used for multiplication/division by 2, which
makes it an arithmetic operation, and which I use to replace certain
exponential operations I used from Lua 5.1/5.2:

        x = 2^30 -- Lua 5.1, 5.2 to get 1073741824

        x = 1<<30 -- Lua 5.3 to get 1073741824

  -spc

Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Oliver Kroth

>    I'm still confused.  Ignoring rotates (which rotate the bits) CPUs tend to
> support two forms of shifting, an unsigned variant (where 0 is copied in for
> right shifts) and a signed variant (where the sign bit is copied for right
> shifts) and are (nominally) used for multiplication/division by 2, which
> makes it an arithmetic operation, and which I use to replace certain
> exponential operations I used from Lua 5.1/5.2:
>
> x = 2^30 -- Lua 5.1, 5.2 to get 1073741824
>
> x = 1<<30 -- Lua 5.3 to get 1073741824
>
>    -spc
>
the difference in unsigned and signed shifting exists only in
right-shifts, where the sign bit, which is at the leftmost position, is
either kept (signed) or filled with zero or carry bit (unsigned)
On left-shifts no two versions are needed.

--
Oliver

Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Sean Conner
It was thus said that the Great Oliver Kroth once stated:

>
> >   I'm still confused.  Ignoring rotates (which rotate the bits) CPUs tend to
> >support two forms of shifting, an unsigned variant (where 0 is copied in for
> >right shifts) and a signed variant (where the sign bit is copied for right
> >shifts) and are (nominally) used for multiplication/division by 2, which
> >makes it an arithmetic operation, and which I use to replace certain
> >exponential operations I used from Lua 5.1/5.2:
> >
> > x = 2^30 -- Lua 5.1, 5.2 to get 1073741824
> >
> > x = 1<<30 -- Lua 5.3 to get 1073741824
> >
> >   -spc
>
> the difference in unsigned and signed shifting exists only in
> right-shifts, where the sign bit, which is at the leftmost position, is
> either kept (signed) or filled with zero or carry bit (unsigned)
> On left-shifts no two versions are needed.

  That, I get.  What I'm replying to is Stefan Ginsberg's statement:

> I don't consider shifting out bits the same thing as overflow, it is
> another type of operation.

  I don't---it's multiplication/division by 2 (in terms of overflow).

  -spc


Reply | Threaded
Open this post in threaded view
|

Re: Some thoughts on integer exponentiation (and an implementation)

Stefan Ginsberg

> On 15 May 2017, at 11:20, Sean Conner <[hidden email]> wrote:
>
> It was thus said that the Great Oliver Kroth once stated:
>>
>> the difference in unsigned and signed shifting exists only in
>> right-shifts, where the sign bit, which is at the leftmost position, is
>> either kept (signed) or filled with zero or carry bit (unsigned)
>> On left-shifts no two versions are needed.
>
>  That, I get.  What I'm replying to is Stefan Ginsberg's statement:
>
>> I don't consider shifting out bits the same thing as overflow, it is
>> another type of operation.
>
>  I don't---it's multiplication/division by 2 (in terms of overflow).
>
>  -spc
>
>

I didn't mean that bit shifts wouldn't correspond to multiplication or division by 2.

However in usage I think of them more as acting on the bits than the "number" itself.

We could be dealing with bit flags, encoded values, or other data where
the series of bits is not interpreted as a number.
For example, a Lua opcode.

From that perspective, I don't consider shifting out bits to be the same thing as overflow.
The usage is different, and shifting out (set) bits is most likely intended.

That is what I meant with "another type of operation".