# Some thoughts on integer exponentiation (and an implementation)

11 messages
Open this post in threaded view
|
Report Content as Inappropriate

## Some thoughts on integer exponentiation (and an implementation)

 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 caseanyone 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.patchAlso from here: https://pastebin.com/iCKGbZnFIn 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 operationto 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!
Open this post in threaded view
|
Report Content as Inappropriate

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

 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
Open this post in threaded view
|
Report Content as Inappropriate

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

 On Sun, May 14, 2017 at 7:02 AM, Dirk Laurie 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.
Open this post in threaded view
|
Report Content as Inappropriate

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

 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.
Open this post in threaded view
|
Report Content as Inappropriate

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

 > 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)'
Open this post in threaded view
|
Report Content as Inappropriate

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

 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
Open this post in threaded view
|
Report Content as Inappropriate

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

 > 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.
Open this post in threaded view
|
Report Content as Inappropriate

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

 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
Open this post in threaded view
|
Report Content as Inappropriate

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

 >    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
Open this post in threaded view
|
Report Content as Inappropriate

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

 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