How to stay in fixnum range?

How to stay in fixnum range?

[Panicz Maciej Godek]

Hi,
I've been writing a program that has something to do with
time processing. It uses the function get-internal-real-time
to measure time in an infinite loop.

I haven't been using running the program long enough to
experience the range-exceeding phenomenon, but I thought
of avoiding it in advance.

The problem may appear when I add some number to the
return value of get-internal-real-time -- what if, during addition,
the scheme fixnum limit is exceeded and the variable becomes
a bignum?

What would be the most efficient solution? Should I compute
the modulo of the sum by a fixnum (or its even divisor) to assure
that the bignum limit is never exceeded?

In low-level programming the case is simple, because the sum
also falls beyond the range as well and no advanced bignum
detection system is ever deployed. Is there a way to achieve the
same effect in guile scheme?

Regards
M.

Re: How to stay in fixnum range?

[Neil Jerram]

2009/1/19 Panicz Maciej Godek <godek.maciek@gmail.com>:
> Hi,
> I've been writing a program that has something to do with
> time processing. It uses the function get-internal-real-time
> to measure time in an infinite loop.
>
> I haven't been using running the program long enough to
> experience the range-exceeding phenomenon, but I thought
> of avoiding it in advance.
>
> The problem may appear when I add some number to the
> return value of get-internal-real-time -- what if, during addition,
> the scheme fixnum limit is exceeded and the variable becomes
> a bignum?

It becomes a bignum.  Why is that a problem?

(Serious question, because the best solution may depend on why this
actually matters...)

      Neil

Re: How to stay in fixnum range?

[Panicz Maciej Godek]

>> The problem may appear when I add some number to the
>> return value of get-internal-real-time -- what if, during addition,
>> the scheme fixnum limit is exceeded and the variable becomes
>> a bignum?
>
> It becomes a bignum.  Why is that a problem?
>
> (Serious question, because the best solution may depend on why this
> actually matters...)

I expect that, after reaching the maximum count (the range of int), the timer
twists back to zero, instead of growing boundlessly.

In that case, the following code may fail:

(define (for-ticks-pass-time-left ticks operation)
  (let ((total-ticks (+ ticks (get-internal-real-time)))
        (elapsed-ticks 0)
        (current-ticks 0)
        (processed-ticks 0))
    (while #t
      (set! current-ticks (get-internal-real-time))
      (set! elapsed-ticks (+ elapsed-ticks (- current-ticks processed-ticks)))
      (set! processed-ticks current-ticks)
      (if (>= elapsed-ticks total-ticks)
        (break))
      (operation (- total-ticks elapsed-ticks)))
    (- elapsed-ticks total-ticks)))

When the internal counter twists back to zero between the
(get-internal-real-time) in the let assignment and in the
while loop, the total-ticks becomes very large, and the
current-ticks is small, so it may take very very long time
for the loop to execute

If all the operations were performed in the modulo
arithmetics (as they are in low level languages), the
problem would solve automatically.

Obviously I could use the modulo division in all the assignments,
but that would cause additional unnecessary overhead.

Probably the best solution would be to implement the
function in C.

Best regards
M

Re: How to stay in fixnum range?

[Ludovic Courtès]

Hello,

Panicz Maciej Godek <godek.maciek@gmail.com> writes:

> If all the operations were performed in the modulo
> arithmetics (as they are in low level languages), the
> problem would solve automatically.

Overflow when doing arithmetic with signed numbers is undefined in C.
See, for instance, GCC's documentation for `-fstrict-overflow'
(info "(gcc) Optimize Options").

Thanks,
Ludo'.

Re: How to stay in fixnum range?

[Neil Jerram]

2009/1/21 Panicz Maciej Godek <godek.maciek@gmail.com>:
>
> I expect that, after reaching the maximum count (the range of int), the timer
> twists back to zero, instead of growing boundlessly.
>
> In that case, the following code may fail:
>
> (define (for-ticks-pass-time-left ticks operation)
>  (let ((total-ticks (+ ticks (get-internal-real-time)))
>        (elapsed-ticks 0)
>        (current-ticks 0)
>        (processed-ticks 0))
>    (while #t
>      (set! current-ticks (get-internal-real-time))
>      (set! elapsed-ticks (+ elapsed-ticks (- current-ticks processed-ticks)))
>      (set! processed-ticks current-ticks)
>      (if (>= elapsed-ticks total-ticks)
>        (break))
>      (operation (- total-ticks elapsed-ticks)))
>    (- elapsed-ticks total-ticks)))

Thanks for explaining.  In terms of the libguile Scheme API, it seems
to me that there isn't currently a good answer to this.  Either we
should implement (get-internal-real-time) such that it doesn't wrap -
which it doesn't look like we do currently - or we should provide
another primitive to indicate what the maximum (and hence wrapping)
value is.

(It may in practice be most-positive-fixnum, but Scheme code shouldn't
have to assume that.)

If you're getting into C code anyway, would you be interested in
writing a libguile patch for this?

Regards,
        Neil

Re: How to stay in fixnum range?

[Andy Wingo]

On Mon 19 Jan 2009 22:02, "Panicz Maciej Godek" <godek.maciek@gmail.com> writes:

> The problem may appear when I add some number to the
> return value of get-internal-real-time -- what if, during addition,
> the scheme fixnum limit is exceeded and the variable becomes
> a bignum?

You could (logand (get-internal-real-time) most-positive-fixnum)

Have you determined when this could happen? most-positive-fixnum can be
quite large on 64-bit machines. I guess you only get 64 days without
bignums on 32-bit machines.

Andy
-- 
http://wingolog.org/