How arbitrary-precision numeric constants are implemented

[Balazs Varga]

Hello,

when I read the new blog post about constants[1] and the
arbitrary-precision numeric numeric constants caught my eye.
I haven't been able to figure out how this feature implemented in the runtime.

Just to give an example from the post:
> Numeric constants live in an arbitrary-precision numeric space; they are just regular numbers. But when they are assigned to a variable the value must be able to fit in the destination. We can declare a constant with a very large value:

> const Huge = 1e1000 // how does it stored, represented?
> fmt.Println(Huge) // overflows float64 - this is OK
> fmt.Println(Huge / 1e999) // this works - how?

I tried to look up in the source (src/cmd/gc/const.c) but I'm not that
familiar with the code base to figure it out myself.

Could somebody be kind to explain it or give some hints where should I
look at? :)

[1]: http://blog.golang.org/constants

Thanks,
Balazs

[Ian Lance Taylor]

On Tue, Aug 26, 2014 at 2:25 PM, Balazs Varga <varb...@gmail.com> wrote:
>
> when I read the new blog post about constants[1] and the
> arbitrary-precision numeric numeric constants caught my eye.
> I haven't been able to figure out how this feature implemented in the runtime.

As you've discovered, it's implemented in the compiler, not the

runtime.


> Just to give an example from the post:
>> Numeric constants live in an arbitrary-precision numeric space; they are just regular numbers. But when they are assigned to a variable the value must be able to fit in the destination. We can declare a constant with a very large value:
>
>> const Huge = 1e1000 // how does it stored, represented?
>> fmt.Println(Huge) // overflows float64 - this is OK
>> fmt.Println(Huge / 1e999) // this works - how?
>
> I tried to look up in the source (src/cmd/gc/const.c) but I'm not that
> familiar with the code base to figure it out myself.

I'm not sure exactly what you are asking. If you are wondering how
the values are represented, see cmd/gc/mparith*.c.

Ian

[Balazs Varga]

Hi Ian,

sorry for not being clear in my previous mail.
I'm trying to rephrase it.

I'm curious how these values are represented in compile time and how
can you do calculations with them without actual types.
I looked at the source files you mentioned but it seems cryptic to me :)

What is the general idea of implementing this feature in the compiler?

Thanks,
Balazs

[Uli Kunitz]

Rob Pike explains the rationale for Go constants in a recent golang.org blog entry. While it doesn't answer your question directly, it is an interesting read and provides the larger background for constants and numeric constants.

 

http://blog.golang.org/constants

 

Having said this I assume that the Go compiler is using a multi-precision library like GMP (gmplib.org) to do the computations. 

 

Uli

 

 

[Balazs Varga]

@Uli, yes, I read the blog post, actually that's why I started this
thread because I see that it works, just don't understand how.
I'll have a look at GMP in the meantime, thanks.

Balazs

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Jesper Louis Andersen]

On Wed, Aug 27, 2014 at 12:10 PM, Uli Kunitz <uli.k...@gmail.com> wrote:

Having said this I assume that the Go compiler is using a multi-precision library like GMP (gmplib.org) to do the computations.

This is far too simple to warrant a library. You can just pick a representation and then pick some naive arithmetic operations on them. It doesn't have to run fast when the only task of the compiler is to map constants into the machine-representation later. Erlang implements large integers by essentially having a radix 2^64 number and then having an array of positions. The basics are in Knuth, The Art of Computer programming Volume 2, Seminumerical algorithms. And for rather simple math, you don't need the optimizations like Karatsuba multiplication, Discrete Cosine Transformation multiplication and so on.

--
J.

[Ian Lance Taylor]

On Wed, Aug 27, 2014 at 2:25 AM, Balazs Varga <varb...@gmail.com> wrote:
>
> I'm curious how these values are represented in compile time and how
> can you do calculations with them without actual types.
> I looked at the source files you mentioned but it seems cryptic to me :)

I'm sorry, I don't know how to make it less cryptic. Perhaps you
could ask a more specific question?

Does it help to look in go.h at the types Mpint, Mpflt, Mpcplx, Val?

Ian

[andrewc...@gmail.com]

Its all in the compiler. Its quite simple to just do all constant calculations at arbitrary precision, then truncate the values to fit into whatever size the compiler is trying to emit.

-1 in arbitrary precision is going to be 0xff as a byte or 0xffffffff as an int32 . There isn't much magic going on.

[adon...@google.com]

On Tuesday, 26 August 2014 17:26:18 UTC-4, Balazs Varga wrote:

Could somebody be kind to explain it or give some hints where should I
look at? :)

As others have pointed out, it's a compile-time thing.  The spec doesn't require arbitrary precision, only >=256 bits.  gc uses 1024 bit integers (Mpint), and floats and complex numbers derived from that (Mpflt, Mpcplx).  The code.google.com/p/go.tools/go/exact package implements constant arithmetic for the go/types frontend used by the llgo compiler; it uses infinite precision rationals.  Each approach has its pros and cons (precision vs time/space complexity).

[Balazs Varga]

Thanks for all the answers! :)

Balazs