integer overflow in J

[John Dixon]

I've recently had a problem with integer overflow in a J-program.  It
caught me unawares because J is usually seems so good at making such
problems invisible by magically changing types.

My problem involves operations with pairs of integers of the form (m, u)
with 1 <: m <: dmax and 0 <: u < 2^m. These pairs represent
{0,1}-strings where  m is the length and u is the integer given by the
binary string. For short integers it is possible to use dmax = 15.  The
concatenation U||V of two strings corresponds to (m,u) concat (n,v) =
((m+n), (u*2^n)+v). One step requires finding (m,u') and (n,v') such
that (u*2^n)+v = (v'*2^m)+u' which is easily solved (in principal) using
the integer quotient-remainder algorithm  {{ (0,x) #: y }}.  However,
for dmax >: 8, J signals an error "x not int" so I am assuming that J
does not switch into full size integers (I am using a 64-bit machine).

Am I right in this interpretation of the behaviour I am seeing? Is it
possible to coerce the short integers into long integers? If it is true
that I need to use short integers, I can rewrite my program but it took
me a while to work out what might have caused "x not int".

I have been using J regularly for over 20 years and appreciate the
enthusiasm and friendliness of the J-community.  Each year J has got
better and I have learned more.

Thanks to all of you who put so much work into J.  It is not only an
amazing and useful construction, but elegant and fun.

        John Dixon

[Remington Furman]

Large integer results promote to floats, not extended precision integers.

Use an "x" suffix to make an extended precision integer (e.g. 1x is
extended).  Then all later operations will use extended precision.

This also surprised me recently, and I wrote about it here (including a
verb to convert log hexadecimal strings to extended precision integers):
https://remcycles.net/blog/bit_errors_j.html

-Remington

> To unsubscribe from this group and stop receiving emails from it, send
> an email to forum+un...@jsoftware.com.
>

[Clifford Reiter]

Note  64 bit integers:

datatype */62#2

integer

but

datatype 2^2

floating

and there are extended integers

datatype 2^2x

extended

[Henry Rich]

I have wondered whether int ^ int should return int if it doesn't overflow.  The current behavior has been around since the beginning.  I have never been able to convince myself that the risk of breaking working code exceeds the value of the change.

Henry Rich

[Devon McCormick]

This may be a case of "If it works, don't fix it."

The current system has gotchas but I think these are pretty well-known.  I will be swiping Cliff's example for next year's NYCJUG meeting as it would be nice to have a reference page somewhere with a list of things to watch out for with automatic type conversion.

--

Devon McCormick

Flâneur

[Michael Day]

So perhaps left shift is the way to do the concatenation,  eg 

lshift =: 34 b.               NB. using fixed width font in email here
NB. concatenate U with V ... 
UcV =: {{)d
'm u' =. x [ 'n v' =. y
(m+n), v + n lshift u
}}
   11 1234 UcV 13 8000 
24 10116928
   #: 1234 8000 10116928
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0
1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0 0
   
Otherwise,  we could use <.@^ which Henry presumably has in mind,   
but that seems a bit inelegant here where we're using only powers of 2. 
Anyway,  extended integers aren't needed for this example.
Should be ok up to 64 bits...  This is the easy bit - don't know 
about solving the step involving u' & v' !

Cheers,

Mike

Virus-free.www.avast.com

[John Dixon]

Thanks to everyone who replied to my request for information about
integers in J (see below).

Summarizing what I learned:

    1. In J integer type is 15-bit (signed integers) [there are also
extended integers which can be much larger but are inevitably slower to
use].  This reflects the underlying implementation of J in C (for a
32-bit machine).

    2. Attempts to use large integers overflows into floating point. In
some cases this maybe harmless but in my case I then tried to use the
floating point to index a list and got "x not int" error.

    3.  In my particular case, once I understood the problem, I have
been able to rewrite my program to avoid the overflow, and it seems to
solve the problem.

    Thank you, John Dixon

[Henry Rich]

In 32-bit J, integers are signed 32-bit.  In 64-bit J, they are signed
64-bit.

Henry Rich