64-bit unsigned integer?

64-bit unsigned integer?

[MM]

Hi

I'm trying to get an unsigned integer type of 64 bits without modular wraparound.

On the GNAT that I have on my OSX, v7.1.0, I have experimented a bit, and can't get it right.

I can declare the type

type u64 is mod 2**64; -- this gives the range of numbers I want, but wraps if It overflows.

I tried 

type u64 is range 0 .. 2**64-1; -- this fails with "integer type definition bounds out of range".

Is there a way to do it so can get an unsigned integer that will raise an exception if it overflows?

By preference, I'm looking for "simple" types (I hope that term is correct) rather than whole new classes. My terminology is heavily influenced by Python - apologies for its lack of accuracy in the Ada world.

M
-- 

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 2018-02-25 13:30, MM wrote:

> I'm trying to get an unsigned integer type of 64 bits without modular wraparound.

Unsigned integers and modular integers are same, mathematically at 
least, considering the semantics of arithmetic operations.

What you want is a [signed] integer subtype of the range 0..2**64-1.

> type u64 is range 0 .. 2**64-1; -- this fails with "integer type definition bounds out of range".

This is the right method alas not supported by the architecture of the 
machine you have.

> Is there a way to do it so can get an unsigned integer that will raise an exception if it overflows?

You must implement it yourself, e.g. on top of a modular or integer 
type, or use an arbitrary length integer arithmetic package. There exist 
a few in Ada.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[MM]

On Sunday, 25 February 2018 12:42:00 UTC, Dmitry Kazakov  wrote:
> On 2018-02-25 13:30, MM wrote:
> > type u64 is range 0 .. 2**64-1; -- this fails with "integer type definition bounds out of range".
> 
> This is the right method alas not supported by the architecture of the 
> machine you have.

Damn. Its a 64-bit CPU; I would have thought that a Carry Or Overflow
bit in the processor would have done the trick?

> > Is there a way to do it so can get an unsigned integer that will raise an
> > exception if it overflows?
> 
> You must implement it yourself, e.g. on top of a modular or integer 
> type, or use an arbitrary length integer arithmetic package. There exist 
> a few in Ada.

I don't want to go the BigNum route - too heavyweight. Implementing it
efficiently myself may require access to the processor's condition code
registers, so this feels like an assembly language approach?

I could overload the arithmetic operators, but this feels icky, particularly
given that regular signed 32- and 64-bit integers overflow "properly", i.e.
with an exception.

M
-- 

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 2018-02-25 13:54, MM wrote:
> On Sunday, 25 February 2018 12:42:00 UTC, Dmitry Kazakov  wrote:
>> On 2018-02-25 13:30, MM wrote:
>>> type u64 is range 0 .. 2**64-1; -- this fails with "integer type definition bounds out of range".
>>
>> This is the right method alas not supported by the architecture of the
>> machine you have.
> 
> Damn. Its a 64-bit CPU; I would have thought that a Carry Or Overflow
> bit in the processor would have done the trick?
> 
>>> Is there a way to do it so can get an unsigned integer that will raise an
>>> exception if it overflows?
>>
>> You must implement it yourself, e.g. on top of a modular or integer
>> type, or use an arbitrary length integer arithmetic package. There exist
>> a few in Ada.
> 
> I don't want to go the BigNum route - too heavyweight. Implementing it
> efficiently myself may require access to the processor's condition code
> registers, so this feels like an assembly language approach?

Why, it is straightforward because you have no negatives. Something like 
this:

    package Unsigneds_64 is
       type u64 is private;
       function "+" (Left, Right : u64) return u64;
       function "-" (Left, Right : u64) return u64;
       function "*" (Left, Right : u64) return u64;
       function "/" (Left, Right : u64) return u64;
    private
       use Interfaces;
       type u64 is new Unsigned_64;
    end Unsigneds_64;

    package body Unsigneds_64 is
       function "+" (Left, Right : u64) return u64 is
          Result : constant u64 :=
                   u64 (Unsigned_64 (Left) + Unsigned_64 (Right));
       begin
          if Result - Left /= Right then
             raise Constraint_Error;
          else
             return Result;
          end if;
       end "+";

       function "-" (Left, Right : u64) return u64 is
       begin
          if Left < Right then
             raise Constraint_Error;
          else
             return u64 (Unsigned_64 (Left) - Unsigned_64 (Right));
          end if;
       end "-";

       function "*" (Left, Right : u64) return u64 is
       begin
          if Left = 0 then
             return 0;
          else
             declare
                Result : constant u64 :=
                         u64 (Unsigned_64 (Left) * Unsigned_64 (Right));
             begin
                if Result / Left /= Right then
                   raise Constraint_Error;
                else
                   return Result;
                end if;
             end;
          end if;
       end "*";

       function "/" (Left, Right : u64) return u64 is
       begin
          return u64 (Unsigned_64 (Left) / Unsigned_64 (Right));
       end "/";

    end Unsigneds_64;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[MM]

On Sunday, 25 February 2018 13:23:24 UTC, Dmitry Kazakov  wrote:
> On 2018-02-25 13:54, MM wrote:
> > I don't want to go the BigNum route - too heavyweight. Implementing it
> > efficiently myself may require access to the processor's condition code
> > registers, so this feels like an assembly language approach?
> 
> Why, it is straightforward because you have no negatives. Something like 
> this:
> 
>     package Unsigneds_64 is

That is a pretty cool solution, and thanks for coding it so quickly!

I was rather hoping for a one-liner type definition, but I suppose I can't have
everything!

M
-- 

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 2018-02-25 14:59, MM wrote:
> On Sunday, 25 February 2018 13:23:24 UTC, Dmitry Kazakov  wrote:
>> On 2018-02-25 13:54, MM wrote:
>>> I don't want to go the BigNum route - too heavyweight. Implementing it
>>> efficiently myself may require access to the processor's condition code
>>> registers, so this feels like an assembly language approach?
>>
>> Why, it is straightforward because you have no negatives. Something like
>> this:
>>
>>      package Unsigneds_64 is
> 
> That is a pretty cool solution, and thanks for coding it so quickly!

Caution, I didn't test it!

> I was rather hoping for a one-liner type definition, but I suppose I can't have
> everything!

Well, what you wrote is legal Ada. It would be nice if RM required such 
things to be always legal even if the hardware would not play with.

P.S. There is a tricky part of intermediate results. RM requires the 
outcome be mathematically correct, it does not require Constraint_Error 
necessarily raised if some intermediate result overflows. The 
implementation like I suggested would always raise Constraint_Error. RM 
approach looks nice mathematically, and also allows optimizations and 
reordering, but that becomes less attractive from the design by contract 
POV as the same code may behave differently on different machines/vendors.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[MM]

On Sunday, 25 February 2018 14:20:18 UTC, Dmitry Kazakov  wrote:
> On 2018-02-25 14:59, MM wrote:
> > That is a pretty cool solution, and thanks for coding it so quickly!
> 
> Caution, I didn't test it!

No worries - I program using TDD. If I use it, it will get a full hammering!

M
-- 

Re: 64-bit unsigned integer?

[Jeffrey R. Carter]

On 02/25/2018 01:54 PM, MM wrote:
> 
> I don't want to go the BigNum route - too heavyweight. Implementing it
> efficiently myself may require access to the processor's condition code
> registers, so this feels like an assembly language approach?

I'm sure the processor has operations that set the overflow flag. You could 
write machine-code insertions that invoke them and check the flag, but that 
doesn't seem like the best way to proceed.

I consider this a fault in the language design. There are two orthogonal 
concepts: whether the representation is signed or not, and whether overflow is 
detected or not. Mixing them together was a mistake.

GNAT had support for 64-bit integers before 64-bit processors were common, so it 
must have chained 2 32-bit integers together. One could hope that, now that 
64-bit processors are common, they'll support 128-bit integers.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail
04

Re: 64-bit unsigned integer?

[Anh Vo]

On Sunday, February 25, 2018 at 4:30:59 AM UTC-8, MM wrote:
> I tried 
> 
> type u64 is range 0 .. 2**64-1; -- this fails with "integer type definition bounds out of range".
> 

It should be: type u64 is range 0 .. 2 **63 - 1;

This is max that GNAT can support on 64 bit architecture. In addition, this is similar to Natural subtype. Look at the standard package for this info.

Anh Vo

Re: 64-bit unsigned integer?

[MM]

On Sunday, 25 February 2018 16:36:47 UTC, Anh Vo  wrote:
> On Sunday, February 25, 2018 at 4:30:59 AM UTC-8, MM wrote:
> > I tried 
> > 
> > type u64 is range 0 .. 2**64-1; -- this fails with "integer type definition bounds out of range".
> > 
> 
> It should be: type u64 is range 0 .. 2 **63 - 1;

That is a 63-bit unsigned, no?

> This is max that GNAT can support on 64 bit architecture.

Apparently :-)

> ... In addition, this is similar to Natural subtype. Look at the standard package for this info.

Will do, thanks.

M
-- 

Re: 64-bit unsigned integer?

[Robert Eachus]

On Sunday, February 25, 2018 at 7:30:59 AM UTC-5, MM wrote:
> Hi
> 
> I'm trying to get an unsigned integer type of 64 bits without modular wraparound.
> 
> On the GNAT that I have on my OSX, v7.1.0, I have experimented a bit, and can't get it right.
> 
> I can declare the type
> 
> type u64 is mod 2**64; -- this gives the range of numbers I want, but wraps if It overflows.

The package that Dmitry is a nice workaround if you really need that particular type.  Decades ago, there was a problem in Ada 83 that you couldn't define a type with the normal modular properties for the largest integer type in number of bits.  Why?  I'd have to go digging through old AIs, but there are places where the unconstrained type (not the subtype) shows up, and they need that one extra bit.

In Ada 95 modular types were introduced to fix this problem.  For embedded systems that was great, there are many hardware registers in various pieces of equipment, and the all usually work with wrap-around semantics.  If they overflow instead?  Define a signed type, and if you have a counter starts at 0 and overflows? Go sort of backwards from Dmitry's solution.  Notice that playing with the arithmetic is only needed for the largest representable integer type.  Represent 0 by -128 and 255 by 127, and do the obvious correction when reading the sensor into a larger computer register.  There is probably more work to convert the reading to a temperature or whatever, and you can do it all in one place.

Compared to trying to force fit a fix through a change in the language definition, the workaround means that another fix seems unnecessary.  Modular types were worth adding for lots of other reasons--I've used them for indexes to hash tables all over the place.

Re: 64-bit unsigned integer?

[Randy Brukardt]

"MM" <mrvmurray@gmail.com> wrote in message 
news:a0147c10-775c-49bf-a0e7-2091f31ac11a@googlegroups.com...
> On Sunday, 25 February 2018 16:36:47 UTC, Anh Vo  wrote:
>> On Sunday, February 25, 2018 at 4:30:59 AM UTC-8, MM wrote:
>> > I tried
>> >
>> > type u64 is range 0 .. 2**64-1; -- this fails with "integer type 
>> > definition bounds out of range".
>> >
>>
>> It should be: type u64 is range 0 .. 2 **63 - 1;
>
> That is a 63-bit unsigned, no?
>
>> This is max that GNAT can support on 64 bit architecture.
>
> Apparently :-)

This is a language limitation. That's because U64'Base is always legal, and 
it has a symmetric signed range. Thus you need the signed values even if you 
never intent to use them.

>> > type u64 is range 0 .. 2**64-1; -- this fails with "integer type 
>> > definition bounds out of range".
>>
>> This is the right method alas not supported by the architecture of the
>> machine you have.
>
>Damn. Its a 64-bit CPU; I would have thought that a Carry Or Overflow
>bit in the processor would have done the trick?

There's not the least bit of difficulty supporting such a thing; the 
Janus/Ada code generator has the needed operations and code generation (for 
32-bit types, no 64-bit integers yet). I'd suspect that the same is true of 
many other code generators.

The problem is simply one of language definition; there is no way in the Ada 
language to get overflow for an unsigned type. Therefore, you can have 
overflow on unsigned representation only so long as there is a (larger) 
signed representation available. (For instance, an overflowing unsigned byte 
representation is fine, as it can use a 16-bit signed base type).

This limitation has always bothered me, but it never has been considered 
important enough to address in the language. These days, we're moving away 
from adding any more kinds of types; everything new will be a library much 
like the containers or the one Dmitry showed. (The reason being that we then 
don't need to define new kinds of generic types.) So I doubt the underlying 
issue will ever be changed.

                                         Randy.

Re: 64-bit unsigned integer?

[MM]

On Monday, 26 February 2018 23:19:24 UTC, Randy Brukardt  wrote:
> This limitation has always bothered me, but it never has been considered 
> important enough to address in the language. These days, we're moving away 
> from adding any more kinds of types; everything new will be a library much 
> like the containers or the one Dmitry showed. (The reason being that we then 
> don't need to define new kinds of generic types.) So I doubt the underlying 
> issue will ever be changed.

Thanks, Randy - nice explanation.

M
-- 

Re: 64-bit unsigned integer?

[Dan'l Miller]

If anyone really needed the processor-overflow-bit-based implementation for speed efficiency, then the presence of Dmitry's IF comparisons for the powers-of-2 corresponding to the unconstrained integer type could conceivably be checked easily as a new local optimization peephole (i.e., use the processor's check-the-overflow-bit test-instruction instead of using the processor's subtraction-based comparison instructions).

If open-source Ada compiler, you could add it yourself (or turn on for Ada that optimization that might exist for C already), and submit it for merge into the repository.  If closed-source Ada compiler, you could pay your vendor to add it.  Either way it is more of an optimizer issue than a language-definition issue.  Either open-source or closer-source way, if you want it badly enough (e.g., because you have hard performance-analysis data to show management), you can expend some money and/or time and make it happen yourself using Dmitry's approach plus overflow-bit-test optimization to make Dmitry's software if statements be a few differences in generated instructions, analogous to multiplying/dividing by powers of 2 being instead generated as shift left/right instructions.  Leveraging the libraries-are-preferred-henceforth view, new optimizer enhancements go hand-in-hand henceforth with each new oft-utilized high-performance-required snippet of source code in a library.  And thus the effort & your audience focus shifts from 1) language architects on the very front end to 2) compiler-backend developers.

Re: 64-bit unsigned integer?

[J-P. Rosen]

Le 27/02/2018 à 17:40, Dan'l Miller a écrit :
> analogous to multiplying/dividing by powers of 2 being instead generated as shift left/right instructions
This is a common error: dividing by 2 is not the same as arithmetic
shifting right (for negative numbers)!

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: 64-bit unsigned integer?

[Dan'l Miller]

Dan'l Miller wrote:
> analogous to multiplying/dividing by powers of 2 being instead generated as shift left/right instructions 

J.P. Rosen wrote:
> This is a common error: dividing by 2 is not the same as arithmetic 
> shifting right (for negative numbers)! 

Failing to read the manual is a common error too.

x86 logical & arithmetic shifting instructions:  http://jsimlo.sk/docs/cpu/index.php/shl.html
x86 roll-shifting instructions: http://jsimlo.sk/docs/cpu/index.php/ror.html
ARM barrel-shifter instructions:  http://www.davespace.co.uk/arm/introduction-to-arm/barrel-shifter.html

Please note that I wrote “instructions” (plural) there, as in the whole family of shift instructions, both logical shift and arithmetic shift.  (I said assembly/machine-code instructions there, not C's crippled shift operators.)  Logical does not preserve 2s-complement representation of negative numbers, but arithmetic does.  In Intel x86 ISA, perhaps you effectively chose SHR instead of SAR.  In ARM ISA, perhaps you effectively chose LSR instead of ASR.  If you are concerned about the rounding down toward negative infinity instead of up toward zero for negative numbers, perhaps ROR and the carry flag are more for you to fix up the rounding via the carry flag as output (after using the CF to shift in the 0 or 1 to maintain the 2s-complement), which is RRX on ARM.  All the while avoiding the more expensive subtraction-comparison operations.

Re: 64-bit unsigned integer?

[Robert Eachus]

On Tuesday, February 27, 2018 at 1:17:07 PM UTC-5, Dan'l Miller wrote:
> Dan'l Miller wrote:

> x86 logical & arithmetic shifting instructions:  http://jsimlo.sk/docs/cpu/index.php/shl.html
> x86 roll-shifting instructions: http://jsimlo.sk/docs/cpu/index.php/ror.html
> ARM barrel-shifter instructions:  http://www.davespace.co.uk/arm/introduction-to-arm/barrel-shifter.html

This is one of those cases where you want to get the code correct, then worry about fast.  You certainly can define your own unsigned type, in a package where the arithmetic operations are provided as assembler functions.  The tricky part is deciding to derive from modular will get you things like loop counters and attributes ('SUCC) that don't work as you expect.  But if you just need an accumulator for fast arriving data, have at it.

Re: 64-bit unsigned integer?

[J-P. Rosen]

Le 27/02/2018 à 19:17, Dan'l Miller a écrit :
> If you are concerned about the rounding down toward negative infinity
> instead of up toward zero for negative numbers, perhaps ROR and the
> carry flag are more for you to fix up the rounding via the carry flag
> as output (after using the CF to shift in the 0 or 1 to maintain the
> 2s-complement), which is RRX on ARM.  All the while avoiding the more
> expensive subtraction-comparison operations.
Yes, that's what I was refering to. I just took this opportunity to
remind that dividing is not equivalent to a "simple" shift operation. Of
course there are ways to generate correct code to fix the difference.

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: 64-bit unsigned integer?

[Paul Rubin]

"Randy Brukardt" <randy@rrsoftware.com> writes:
> The problem is simply one of language definition; there is no way in
> the Ada language to get overflow for an unsigned type... These days,
> we're moving away from adding any more kinds of types; everything new
> will be a library much like the containers

That seems unfortunate.  I hope the libraries can be implemented in a
way that don't cause runtime overhead.  C unsigned ints wrap around but
that is bogus since it kills the invariant that n+1 is always greater
than n.  GHC has a Word type that wraps around, for when you want
wraparound, but Integers are (arbitrary precision) integers.  (Plus
there is also an evil and unsafe machine-word Int type).

Having an unsigned int type that 1) uses all the bits in the machine
word, and 2) errors on overflow, plus a separd Word type that wraps
around, seems like the right way to do things.  Oh well.

Re: 64-bit unsigned integer?

[J-P. Rosen]

Le 28/02/2018 à 11:17, Paul Rubin a écrit :
> Having an unsigned int type that 1) uses all the bits in the machine
> word, and 2) errors on overflow, plus a separd Word type that wraps
> around, seems like the right way to do things.  Oh well.
That would certainly raise many issues. For example, this type would
certainly not have a unary minus... and if a negative result is found in
intermediate calculations, C_E should be raised.

Totally different arithmetic => a new kind of integer type. Just for the
sake of a single (albeit important sometimes) use case.

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 28/02/2018 11:39, J-P. Rosen wrote:
> Le 28/02/2018 à 11:17, Paul Rubin a écrit :
>> Having an unsigned int type that 1) uses all the bits in the machine
>> word, and 2) errors on overflow, plus a separd Word type that wraps
>> around, seems like the right way to do things.  Oh well.
> That would certainly raise many issues. For example, this type would
> certainly not have a unary minus... and if a negative result is found in
> intermediate calculations, C_E should be raised.
> 
> Totally different arithmetic => a new kind of integer type. Just for the
> sake of a single (albeit important sometimes) use case.

On top of that, I think that overflow check in this and similar cases is 
not a problem but a solution born out of necessity. Actually, required 
is absence of overflows, not catching them at run-time. Thus a 
combination of SPARK and a 64-bit modular type could be a far better 
approach.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[Randy Brukardt]

"Paul Rubin" <no.email@nospam.invalid> wrote in message 
news:877eqxe7u8.fsf@nightsong.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>> The problem is simply one of language definition; there is no way in
>> the Ada language to get overflow for an unsigned type... These days,
>> we're moving away from adding any more kinds of types; everything new
>> will be a library much like the containers
>
> That seems unfortunate.  I hope the libraries can be implemented in a
> way that don't cause runtime overhead.

I don't see any reason why not. Just because something is in a library 
doesn't prevent it from using inlining, which then opens the door to all of 
the "normal" optimizations.

One of the main reason for the change to libraries is that we have a number 
of requests to add additional numeric functionality (unlimited-size integers 
["bignum"], saturation math) and dealing with all of those with dedicated 
types would add a load of built-in stuff and complications. (It also would 
make generic sharing much harder, possibly impossible, depending on the 
rules adopted.)

Libraries pretty much avoid all of that, and can be implemented as well (or 
poorly) as makes sense for an Ada vendor (meaning that they don't have to 
expend much in the way of resources on features not of interest to their 
customers).

                                                     Randy.

Re: 64-bit unsigned integer?

[Paul Rubin]

"Randy Brukardt" <randy@rrsoftware.com> writes:
> One of the main reason for the change to libraries is that we have a number 
> of requests to add additional numeric functionality (unlimited-size integers 
> ["bignum"], saturation math) 

I'd imagine that in the Ada world, machine integers should have a more
primitive status than that of bignums.  That's because bignum arithmetic
can allocate hard-to-predict amounts of memory and take unknown runtime,
in tension with Ada's emphasis on resource control and realtime
predictability.

Re: 64-bit unsigned integer?

[Niklas Holsti]

On 18-03-01 07:47 , Paul Rubin wrote:
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>> One of the main reason for the change to libraries is that we have a number
>> of requests to add additional numeric functionality (unlimited-size integers
>> ["bignum"], saturation math)
>
> I'd imagine that in the Ada world, machine integers should have a more
> primitive status than that of bignums.

As long as the new numeric libraries let us write computations using the 
normal algebraic syntax (A * B + C), I have nothing against library 
solutions.

> That's because bignum arithmetic
> can allocate hard-to-predict amounts of memory and take unknown runtime,
> in tension with Ada's emphasis on resource control and realtime
> predictability.

Following the trend set by recent Ada standard extensions, there could 
be a "bounded" version of the "bignum" library.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: 64-bit unsigned integer?

[Simon Wright]

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:

> As long as the new numeric libraries let us write computations using
> the normal algebraic syntax (A * B + C), I have nothing against
> library solutions.

See Ada.Numerics.Generic_Real_Arrays.

Also, operator precedence is defined by the operator, not the package in
which it's declared for a particular type.

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 01/03/2018 09:16, Niklas Holsti wrote:

> Following the trend set by recent Ada standard extensions, there could 
> be a "bounded" version of the "bignum" library.

That replaces unpredictable penalty with a predictably prohibitive one. 
Shuffling arrays of machine words for each arithmetic operation is a 
non-starter.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[Dan'l Miller]

Dmitry A. Kazakov wrote:
> That replaces unpredictable penalty with a predictably prohibitive one. 

Why is it prohibitive?

> Shuffling arrays of machine words for each arithmetic operation is a 
>  non-starter. 

What precisely is “shuffling” here?  (Certainly pejorative slang here, not shuffling as in cards.)  Bignum integers would simply be a binary form of string where the library performs for modern processors an extrapolation of what we used to do on 6502 processors to get more than 8-bit arithmetic:  e.g., for addition, add each N-bit “digit” as in elementary-school-esque positional-numeral addition notation plus carry-flag from the N-bit digit to the immediate right, where N=8 on 8-bit processors that lacked 16-bit or 32-bit arithmetic instructions such as the 6502, N=64 on 64-bit processors, and N=32 on 32-bit processors.  I'm not seeing the “shuffling” problem here; bignum's array of machine words just looks like garden-variety positional numerals, merely in an enormous radix-base instead of base 2, 8, 10, or 16 for each digit that human beings consider convenient for manual arithmetic calculations.  And there was a time as recently as the mid-1980s with 6502-family processors where nearly •every• serious programmer on that platform just knew how to manage bignum-esque arithmetic in base 256, because that is effectively how we did 16-bit and 32-bit arithmetic on the 6502.

As such, perhaps yes, setting an upper bound on the size of each bignum array is desirable and perhaps the more-mainstream case compared to unbounded, so that, say, O(nˣ) operations have a knowable maximum computation time (as well as the obvious maximum memory allocation) at engineering-time for x > 1.  Also, perhaps knowing that I am going to get exactly 128-bit integers makes some other portion of the design more practical (e.g., record layout where the 128-bit integer is placed in situ within the record, instead of allocated separately as potentially-varying size).

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 2018-03-01 19:15, Dan'l Miller wrote:
> Dmitry A. Kazakov wrote:
>> That replaces unpredictable penalty with a predictably prohibitive one.
> 
> Why is it prohibitive?

Because a bounded-length number object will have the worst case length, 
always. E.g. 100 x 64-bit words. Each elementary operation will take 
1600 bytes from the stack and return 800 bytes back. This is certainly 
not for a small embedded/real-time target.

But surely any range must be supported regardless the target hardware. 
Why invent a bicycle? Just allow

    type Big is range -2**6399..2**6399-1;

No bounded-length numbers ever needed.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[Dan'l Miller]

Dmitry Kazakov wrote:
> Because a bounded-length number object will have the worst case length, always.

Why would they be allocated as the humanly-imaginable worst-case for usage of the library?  Bounded textual strings are not allocated as the maximum universally-conceivable textual string length of megabytes long.  Bounded simply means:  pick a modest upper bound and stick to it, say, 128-bit integer for bounded bignum or 32-character string for bounded textual string.

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 2018-03-01 20:22, Dan'l Miller wrote:
> Dmitry Kazakov wrote:
>> Because a bounded-length number object will have the worst case length, always.
> 
> Why would they be allocated as the humanly-imaginable worst-case for usage of the library?

Because the upper bound is exactly that, the humanly-imaginable worst case.

> Bounded textual strings are not allocated as the maximum universally-conceivable textual string length of megabytes long.  Bounded simply means:  pick a modest upper bound and stick to it, say, 128-bit integer for bounded bignum or 32-character string for bounded textual string.

Why 128 and not 256 or 1056781?

And note that all this a bit pointless in the discussion context, which 
was about overflow checks. When the upper bound is known, then checks 
are superfluous. Otherwise, there is no need to carry many digits 
because you expect overflows occasionally.

So I prefer SPARK to guarantee absence of overflows and a more 
reasonable support of modestly big ranges.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[Niklas Holsti]

On 18-03-01 21:10 , Dmitry A. Kazakov wrote:
> On 2018-03-01 19:15, Dan'l Miller wrote:
>> Dmitry A. Kazakov wrote:
>>> That replaces unpredictable penalty with a predictably prohibitive one.
>>
>> Why is it prohibitive?
>
> Because a bounded-length number object will have the worst case length,
> always. E.g. 100 x 64-bit words. Each elementary operation will take
> 1600 bytes from the stack and return 800 bytes back. This is certainly
> not for a small embedded/real-time target.
>
> But surely any range must be supported regardless the target hardware.
> Why invent a bicycle? Just allow
>
>    type Big is range -2**6399..2**6399-1;

I agree that such a built-in, non-library solution would be preferable 
from the programmer's point of view. But it could have consequences in 
other parts of the language which depend on the size of the largest 
integer type, and that could make it harder for a compiler to support 
the above form than to support a "bignum" library, bounded or unbounded.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: 64-bit unsigned integer?

[Dan'l Miller]

Dan'l Miller wrote:
> > Why would they be allocated as the humanly-imaginable worst-case for usage of the library? 
Dmitry Kazakov wrote:
> Because the upper bound is exactly that, the humanly-imaginable worst case. 

No, the upper bound of a bounded integer (or bounded string for that matter) is what I declared it to be in my own app-domain source code.  The upper-bound is not what other human beings on the planet would like to declare it to be in their app-domain source code.

Dan'l Miller wrote:
> > Bounded textual strings are not allocated as the maximum universally-conceivable textual string length of megabytes long.  Bounded simply means:  pick a modest upper bound and stick to it, say, 128-bit integer for bounded bignum or 32-character string for bounded textual string. 
Dmitry Kazakov wrote:
> Why 128 and not 256 or 1056781? 

Because I declared it to be a 128-bit bounded bignum at this place in my app-domain source code for some register in my main processor, and I declared some other 256-bit bounded bignums at some other place in my app-domain source code for some other register in my GPU.  And in this application, the calculations on the 128-bit bounded bignums never utilize the 256-bit bounded bignums, and the calculations on the 256-bit bounded bignums never utilize the 128-bit bounded bignums; they are disjoint usages.  Why does bounded mean for you “one size fits all for all human beings on the planet”?  Bounded means instead the fixed nonvarying size of this instance as declared in each locality of app-domain source code, not in the library (or in the language reference manual, for that matter) for all human beings on the planet.

Re: 64-bit unsigned integer?

[Dmitry A. Kazakov]

On 2018-03-01 21:32, Dan'l Miller wrote:
> Dan'l Miller wrote:
>>> Why would they be allocated as the humanly-imaginable worst-case for usage of the library?
> Dmitry Kazakov wrote:
>> Because the upper bound is exactly that, the humanly-imaginable worst case.
> 
> No, the upper bound of a bounded integer (or bounded string for that matter) is what I declared it to be in my own app-domain source code.

You are a human and it is your imagination which gave you the bound value.

> Dan'l Miller wrote:
>>> Bounded textual strings are not allocated as the maximum universally-conceivable textual string length of megabytes long.  Bounded simply means:  pick a modest upper bound and stick to it, say, 128-bit integer for bounded bignum or 32-character string for bounded textual string.
> Dmitry Kazakov wrote:
>> Why 128 and not 256 or 1056781?
> 
> Because I declared it to be a 128-bit bounded bignum at this place in my app-domain source code for some register in my main processor, and I declared some other 256-bit bounded bignums at some other place in my app-domain source code for some other register in my GPU.  And in this application, the calculations on the 128-bit bounded bignums never utilize the 256-bit bounded bignums, and the calculations on the 256-bit bounded bignums never utilize the 128-bit bounded bignums; they are disjoint usages.  Why does bounded mean for you “one size fits all for all human beings on the planet”?

Bounded numbers will be a generic package thus you will not be able to 
intermix differently bounded numbers even if they are semantically same. 
You will not be able to convert between such types. You will have no 
literals, no universal integer expressions, no way to pass it to a 
generic numeric package, no way to have it as discriminant (large 
discriminants are useful in some cases) etc.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: 64-bit unsigned integer?

[Randy Brukardt]

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:ffpr62F1cdeU1@mid.individual.net...
> On 18-03-01 07:47 , Paul Rubin wrote:
>> "Randy Brukardt" <randy@rrsoftware.com> writes:
>>> One of the main reason for the change to libraries is that we have a 
>>> number
>>> of requests to add additional numeric functionality (unlimited-size 
>>> integers
>>> ["bignum"], saturation math)
>>
>> I'd imagine that in the Ada world, machine integers should have a more
>> primitive status than that of bignums.
>
> As long as the new numeric libraries let us write computations using the 
> normal algebraic syntax (A * B + C), I have nothing against library 
> solutions.

Of course. Ada allows operator overloading and is expected to allow numeric 
literal overloading, too.

>> That's because bignum arithmetic
>> can allocate hard-to-predict amounts of memory and take unknown runtime,
>> in tension with Ada's emphasis on resource control and realtime
>> predictability.
>
> Following the trend set by recent Ada standard extensions, there could be 
> a "bounded" version of the "bignum" library.

That's the plan for the integer version. To date, we haven't been able to 
figure out meaningful semantics for a bounded rational library, so we're not 
planning on one of those. (The problem being what to do when you reach the 
bounds. Some sort of rounding seems necessary, but that would violate the 
premise of extra mathmatical results.)

                             Randy.

Re: 64-bit unsigned integer?

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:p79qhc$7vu$1@gioia.aioe.org...
...
[Answered based on the most recent thinking, but this is a long way from 
done. - RLB]

> Bounded numbers will be a generic package thus you will not be able to 
> intermix differently bounded numbers even if they are semantically same. 
> You will not be able to convert between such types.

Directly, definitely true. Indirectly, probably not true. You can always 
convert to be unbounded integer or to a "machine" integer.

> You will have no literals,

False: all of these package will have literals (and you will be able to add 
them to any private type of yours as well).

> no universal integer expressions,

Universal integer expressions are completely separate from any math issues 
(since they're evaluated as, well, universal integer expressions). One would 
hope these would work (if not, it seems that we have something that needs to 
be fixed).

> no way to pass it to a generic numeric package

That's an advantage, not a disadvantage. (You always say that you hate 
generics anyway, why do you care??)
Ada doesn't have a universal generic formal numeric type, and that a good 
thing -- it would be virtually impossible to reason about the semantics of 
such a type. (Overflow, saturation, or neither? Floating precision/fixed 
precision/exact results? Etc.)

Also, from an implementation perspective, such a thing would make shared 
generics totally unusable (every operation would have to be done in a thunk, 
as the various differences noted above could not be reconciled with the 
usual technique of "use the largest representation"). That makes me against 
it as it represents an existential threat to Janus/Ada.

>, no way to have it as discriminant (large discriminants are useful in some 
>cases)

Thank goodness. The fewer discriminants the better.

The same would be true with array indexing (although you could use it as a 
map key to get a similar effect).

                                 Randy.

Re: 64-bit unsigned integer?

[Robert Eachus]

On Thursday, March 1, 2018 at 4:15:28 PM UTC-5, Dmitry A. Kazakov wrote:

> Bounded numbers will be a generic package thus you will not be able to 
> intermix differently bounded numbers even if they are semantically same. 
> You will not be able to convert between such types. You will have no 
> literals, no universal integer expressions, no way to pass it to a 
> generic numeric package, no way to have it as discriminant (large 
> discriminants are useful in some cases) etc.

Try this:

type Bignum_Value is array(Long_Integer range <>) of Long_Integer;
type Access_Bignum is access Bignum_Value;
Default_Max_Size: Long_Integer;

type Bounded_Bignum (Size: Long_Integer := 0) is record
     case Size is 
       when 0..Default_Max_Size =>
          Bounded_Value: Bignum_Value(1..Default_Max_Size);
       when others => Access_Bignum;
     end case;
   end record;

Hide this all as appropriate, in a private part, and define the operations.  Overflow is handled by switching representations, and the Default_Max_Size can be tuned by the user for best results in his or her program.  Well, to be honest overflow can happen.  If Long_Integer is 64 bits, then you will run out of memory long before you hit that limit.  Even if the computer supports full 64-bit virtual memory, and you have the disk space, the type specified here should support 2**67 bytes in one value.  Mathematicians worry about things like this, so you might want to have an machine attribute of the number of bits of the largest value that can be crammed into (virtual) memory.