Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3281

Re: 64 bit, unsigned integer arithmetic in PostScript

Show all headers | View raw

On Sunday, 15 July 2018 00:54:29 UTC+1, John Reiser  wrote:
> > https://github.com/bwipp/postscriptbarcode/blob/b4520c7184e08cc8ea17b4d7f50cd5ffe49f0ff2/contrib/development/lcg64_temper.ps
> 
> The shifting of two 16-bit [unsigned] numbers in function bitshift2() is tedious.
> Instead, shift a native Postscript 32-bit signed integer in function temper(),
> and correct for sign extension (AND-off the propagated sign bit) when the input
> has the high bit set and the shift count is negative (thus a right shift).
> It can be simpler and faster to do the AND for all right shifts, even though
> a positive input will not need it.

Thanks. My latest version (just committed) does that - the lcg64_temper procedure returns correct 32-bit patterns, albeit with PostScript representing this in signed format (and I'm currently forcing 64 bit into the same range, which might be a temporary feature):

https://github.com/bwipp/postscriptbarcode/blob/master/contrib/development/lcg64_temper.ps

> In regards to a comment from the code:
>     > % Avoid 15-bit overflow when multiplying the digits by stealing from the second digit
> A major point of my earlier comment about   > 15 x 16 ==> 31 bits with no overflow in signed 32-bit arithmeticis: once the multiplier 6364136223846793005 == 0x5851_f42d_4c95_7f2d
> has been re-coded by replacing 0xf42d by (0x10000 - 0x0bd3) then the
> previous value of the 'seed' variable needs only to be split into
> four 16-bit digits, and does not require re-coding even though a digit
> may have its bit 15 (0x8000) set.  There are (4+3+2+1) multiplies using 16 bits
> from seed and 15 bits from the multiplier; each multiply giving 31 bits
> and thus no overflow in 32-bit Postscript signed integers.  Only the compile-time
> re-coding of the constant multiplier is necessary; the dynamic digits of 'seed'
> never need re-coding.

I need to read this carefully (not at 1:30AM!) but I think my code does what you state. The "borrowing" that I refer to in the comment is a representation of the multiplier in the source rather than a repeated runtime activity. (I do also borrow elsewhere from each digit but that's to force the digits representing the sum of the products to be positive to simplify the carry code, so there might be an optimisation/simplification here.)

> > The C code provided by the specification (trimmed version below) converts the uint32_t output of lcg64_temper to a float, then divides by 2^32-1, before multiplying and recasting to an int32_t. Unless I'm missing something fundamental it seems as though this process will lead to irrecoverable loss of precision that will cause rounding differences between implementations...
> 
> > int main() {
> >      int32_t data_length=1234;  /* Dummy, up to ~27000 bits */
> >      lcg64_seed = 226759;
> >      for (int32_t i=0; i < data_length; i++) {
> >          int32_t pos = (int32_t)( (float)lcg64_temper() / (float)UINT32_MAX * (data_length-i) );
> 
> There are some misconceptions in the quoted plain text [above] which precedes the quoted code.
> The value of (float)UINT32_MAX is exactly 2**32 because the IEEE-754 conversion is rounded.
> The value of (float)lcg64_temper() also is rounded to 24 bits of precision from [upto] 32 bits.
> In nearly all cases this loses some precision, but there is no ambiguity in the result
> because IEEE-754 specifies the rules which generate a repeatable result.
> The division of those two floats is exact (merely subtract exponents).
> The multiplication by (data_length - i) incurs some rounding of the 48-bit
> intermediate mantissa to the 24 bits of a 'float'.  Again, IEEE-754 guarantees
> the same result in all implementations.  The final conversion from float to int32_t is exact.
> [If the implementation of the floating-point operations used here does not conform
> to IEEE-754 then the implementation is not worth anyone's time or money.  Really!]

Thanks again! I'll digest this and echo back my understanding with code.


All the best,

Terry

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

64 bit, unsigned integer arithmetic in PostScript Terry Burton <terry.burton@gmail.com> - 2018-07-04 15:25 -0700
  Re: 64 bit, unsigned integer arithmetic in PostScript luser droog <luser.droog@gmail.com> - 2018-07-05 11:25 -0700
  Re: 64 bit, unsigned integer arithmetic in PostScript John Reiser <vendor@BitWagon.com> - 2018-07-06 19:53 -0700
    Re: 64 bit, unsigned integer arithmetic in PostScript Terry Burton <terry.burton@gmail.com> - 2018-07-09 18:01 -0700
      Re: 64 bit, unsigned integer arithmetic in PostScript Terry Burton <terry.burton@gmail.com> - 2018-07-12 01:38 -0700
        Re: 64 bit, unsigned integer arithmetic in PostScript John Reiser <vendor@BitWagon.com> - 2018-07-14 16:54 -0700
          Re: 64 bit, unsigned integer arithmetic in PostScript Terry Burton <terry.burton@gmail.com> - 2018-07-14 17:40 -0700
            Re: 64 bit, unsigned integer arithmetic in PostScript Terry Burton <terry.burton@gmail.com> - 2018-07-16 16:03 -0700
              Re: 64 bit, unsigned integer arithmetic in PostScript John Reiser <vendor@BitWagon.com> - 2018-07-16 21:19 -0700

csiph-web