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

Groups > comp.lang.c > #138493 > unrolled thread

Big integers

Back to article view | Back to comp.lang.c

Contents

  Big integers Bart <bc@freeuk.com> - 2018-12-04 12:17 +0000
    Re: Big integers fir <profesor.fir@gmail.com> - 2018-12-04 05:58 -0800
      Re: Big integers Chad <cdalten@gmail.com> - 2018-12-04 08:22 -0800
        Re: Big integers Bart <bc@freeuk.com> - 2018-12-04 17:04 +0000
          Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-04 17:19 +0000
    Re: Big integers Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2018-12-04 08:38 -0800
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-04 17:35 +0000
        Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-04 18:13 +0000
          Re: Big integers "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-04 10:50 -0800
          Re: Big integers Rosario19 <Ros@invalid.invalid> - 2018-12-06 17:56 +0100
        Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-04 10:22 -0800
          Re: Big integers Eli the Bearded <*@eli.users.panix.com> - 2018-12-04 18:58 +0000
            Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-04 11:32 -0800
              Re: Big integers Eli the Bearded <*@eli.users.panix.com> - 2018-12-04 22:45 +0000
                Re: Big integers jameskuyper@alumni.caltech.edu - 2018-12-04 14:57 -0800
            Re: Big integers jameskuyper@alumni.caltech.edu - 2018-12-04 12:14 -0800
            Re: Big integers chris.m.thomasson.1@gmail.com - 2018-12-04 16:58 -0800
              Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-05 03:14 +0000
                Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-05 14:27 -0800
              Re: Big integers Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2018-12-04 20:03 -0500
                Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-05 14:25 -0800
        Re: Big integers jacob navia <jacob@jacob.remcomp.fr> - 2018-12-04 23:45 +0100
          Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-04 23:29 +0000
          Re: Big integers Bart <bc@freeuk.com> - 2018-12-05 00:30 +0000
            Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-05 14:28 -0800
          Re: Big integers Jens Stuckelberger <Jens_Stuckelberger@nowhere.net> - 2018-12-05 17:50 +0000
            Re: Big integers jacobnavia <jacob@jacob.remcomp.fr> - 2018-12-05 20:03 +0100
          Re: Big integers Keith Thompson <kst-u@mib.org> - 2018-12-05 13:46 -0800
            Re: Big integers jacobnavia <jacob@jacob.remcomp.fr> - 2018-12-06 06:41 +0100
              Re: Big integers Keith Thompson <kst-u@mib.org> - 2018-12-05 22:40 -0800
    Re: Big integers "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-04 09:08 -0800
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-04 19:41 +0000
        Re: Big integers "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-04 12:00 -0800
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-08 11:28 +0000
    Re: Big integers Ian Collins <ian-news@hotmail.com> - 2018-12-05 15:19 +1300
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-05 11:58 +0000
        Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-05 14:35 +0100
          Re: Big integers Bart <bc@freeuk.com> - 2018-12-05 14:35 +0000
            Re: Big integers Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2018-12-05 07:39 -0800
              Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-05 07:45 -0800
                Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-05 17:51 +0000
                  Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-05 22:19 +0100
                Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-05 14:55 -0800
                  Re: Big integers jameskuyper@alumni.caltech.edu - 2018-12-05 15:19 -0800
                    Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-05 16:13 -0800
                      Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-06 09:35 +0100
                        Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-07 14:26 -0800
                          Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-07 19:56 -0800
                  Re: Big integers James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-09 12:01 -0500
                    Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-10 14:47 -0800
                      Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-11 00:50 +0000
                        Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-10 17:37 -0800
                          Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-14 21:18 -0800
            Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-05 07:57 -0800
            Re: Big integers Bart <bc@freeuk.com> - 2018-12-05 15:59 +0000
              Re: Big integers Bart <bc@freeuk.com> - 2018-12-05 22:59 +0000
                Re: Big integers jameskuyper@alumni.caltech.edu - 2018-12-05 15:31 -0800
                  Re: Big integers Robert Wessel <robertwessel2@yahoo.com> - 2018-12-05 20:03 -0600
                Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-05 23:42 +0000
                  Re: Big integers James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-05 20:15 -0500
                Re: Big integers Ike Naar <ike@iceland.freeshell.org> - 2018-12-10 07:26 +0000
                  Re: Big integers Bart <bc@freeuk.com> - 2018-12-10 18:38 +0000
                    Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-10 19:10 +0000
                      Re: Big integers Bart <bc@freeuk.com> - 2018-12-10 21:23 +0000
                    Re: Big integers Ike Naar <ike@iceland.freeshell.org> - 2018-12-10 22:47 +0000
            Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-05 22:15 +0100
          Re: Big integers Bart <bc@freeuk.com> - 2018-12-06 13:43 +0000
            Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-06 07:50 -0800
        Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-05 15:19 +0000
          Re: Big integers luser droog <luser.droog@gmail.com> - 2018-12-10 23:19 -0800
            Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-11 08:45 +0100
              Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-11 11:15 +0000
                Re: Big integers Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2018-12-11 04:36 -0800
                  Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-11 14:35 +0100
                Re: Modules again (was: Big integers) Bart <bc@freeuk.com> - 2018-12-11 12:53 +0000
                  Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-11 14:45 +0100
                    Re: Modules again Bart <bc@freeuk.com> - 2018-12-11 16:08 +0000
                      Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-11 21:37 +0100
                    Re: Modules again Thiago Adams <thiago.adams@gmail.com> - 2018-12-11 08:59 -0800
                      Re: Modules again Bart <bc@freeuk.com> - 2018-12-11 17:49 +0000
                      Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-11 21:44 +0100
                    Re: Modules again scott@slp53.sl.home (Scott Lurndal) - 2018-12-11 18:02 +0000
                      Re: Modules again Thiago Adams <thiago.adams@gmail.com> - 2018-12-11 10:10 -0800
                        Re: Modules again scott@slp53.sl.home (Scott Lurndal) - 2018-12-11 18:54 +0000
                      Re: Modules again Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2018-12-11 13:14 -0500
                        Re: Modules again scott@slp53.sl.home (Scott Lurndal) - 2018-12-11 18:54 +0000
                          Re: Modules again Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2018-12-11 14:42 -0500
                            Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-11 21:54 +0100
                              Re: Modules again Keith Thompson <kst-u@mib.org> - 2018-12-11 14:53 -0800
                                Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-12 08:24 +0100
                      Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-11 21:51 +0100
                        Re: Modules again scott@slp53.sl.home (Scott Lurndal) - 2018-12-11 23:24 +0000
                          Re: Modules again Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2018-12-11 18:44 -0500
                            Re: Modules again Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2018-12-11 18:45 -0500
                            Re: Modules again Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-12-12 06:39 +0000
                              Re: Modules again James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-12 07:59 -0500
                                Re: Modules again mark.bluemel@gmail.com - 2018-12-12 05:43 -0800
                                Re: Modules again scott@slp53.sl.home (Scott Lurndal) - 2018-12-12 14:20 +0000
                                Re: Modules again David Brown <david.brown@hesbynett.no> - 2018-12-12 17:10 +0100
                                  Re: Modules again James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-12 13:39 -0800
                            Re: Modules again scott@slp53.sl.home (Scott Lurndal) - 2018-12-12 14:19 +0000
                              Re: Modules again Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2018-12-12 10:28 -0500
        Re: Big integers Ian Collins <ian-news@hotmail.com> - 2018-12-06 08:10 +1300
          Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-05 20:57 +0000
            Re: Big integers Ian Collins <ian-news@hotmail.com> - 2018-12-06 10:16 +1300
              Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-05 23:15 +0000
                Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-05 23:44 +0000
    Re: Big integers Robert Wessel <robertwessel2@yahoo.com> - 2018-12-05 02:51 -0600
    Re: Big integers antispam@math.uni.wroc.pl - 2018-12-07 15:26 +0000
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-07 16:27 +0000
        Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-07 16:36 +0000
          Re: Big integers Bart <bc@freeuk.com> - 2018-12-07 17:01 +0000
        Re: Big integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-12-07 17:55 +0000
        Re: Big integers antispam@math.uni.wroc.pl - 2018-12-07 19:26 +0000
          Re: Big integers Bart <bc@freeuk.com> - 2018-12-07 21:39 +0000
            Re: Big integers Ian Collins <ian-news@hotmail.com> - 2018-12-08 10:51 +1300
    Re: Big integers Anton Shepelev <anton.txt@gmail.com> - 2018-12-08 00:43 +0300
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-08 01:08 +0000
      Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-08 15:13 +0100
        Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-08 15:15 +0100
          Re: Big integers Bart <bc@freeuk.com> - 2018-12-08 14:48 +0000
            Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-10 05:10 -0800
              Re: Big integers Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2018-12-10 05:22 -0800
                Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-10 15:27 +0100
                  Re: Big integers scott@slp53.sl.home (Scott Lurndal) - 2018-12-10 15:59 +0000
                  Re: Big integers antispam@math.uni.wroc.pl - 2018-12-11 21:14 +0000
              Re: Big integers Bart <bc@freeuk.com> - 2018-12-10 14:56 +0000
                Re: Big integers Ike Naar <ike@iceland.freeshell.org> - 2018-12-10 17:46 +0000
                  Re: Big integers Bart <bc@freeuk.com> - 2018-12-10 18:24 +0000
                    Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-10 11:12 -0800
                      Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-10 11:23 -0800
                      Re: Big integers Bart <bc@freeuk.com> - 2018-12-10 21:44 +0000
                        Re: Big integers Thiago Adams <thiago.adams@gmail.com> - 2018-12-11 10:20 -0800
                          Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-11 13:15 -0800
        Re: Big integers Keith Thompson <kst-u@mib.org> - 2018-12-08 12:14 -0800
          Re: Big integers David Brown <david.brown@hesbynett.no> - 2018-12-09 13:31 +0100
        Re: Big integers "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-08 15:52 -0800
    Re: Big integers Bart <bc@freeuk.com> - 2018-12-16 19:29 +0000
    Re: Big integers "Tristan B. Kildaire" <deavmi@disroot.org> - 2018-12-25 12:59 +0000
      Re: Big integers Bart <bc@freeuk.com> - 2018-12-25 15:54 +0000

Page 2 of 7 — ← Prev page 1 [2] 3 4 5 6 7  Next page →

#138558

On 12/4/2018 5:03 PM, Lew Pitcher wrote:
> chris.m.thomasson.1@gmail.com wrote:
> 
>> On Tuesday, December 4, 2018 at 10:58:57 AM UTC-8, Eli the Bearded wrote:
>>> In comp.lang.c, Thiago Adams  <thiago.adams@gmail.com> wrote:
>>>> Every float point number is a fraction,
>>>
>>> How do you reconcile that statement with the definition of an
>>> "irrational number"?
>>>
>>> Elijah
>>> ------
>>> just curious
>>
>> Fwiw, an arbitrary precision real can be the convergent of a continued
>> fraction up to a user provided precision. For instance:
>> ____________________
>> PI           = 3.1415926535897932384626433832795[...]
>> 22/7         = 3.14        ; 2 points of precision
>> 333/106      = 3.1415      ; 4 points of precision
> 
>    355/113      = 3.141592    ; 6 points of precision

Big time. For some reason I forgot about that one.



> 
> 
>> 103993/33102 = 3.141592653 ; 9 points of precision
>> ____________________
>>
>> If a user asks for pi with at least 3 points of precision, we can give
>> them 333/106. ;^)
> 
>>
>> // posting from my gmail account, my Usenet server is acting funny right
>> now.
> 
> 

[toc] | [prev] | [next] | [standalone]

#138513

Le 04/12/2018 à 18:35, Bart a écrit :> An extended precision floating 
point library would also be intriguing to
 > write. But it can't be arbitrary precision. (How many digits to
 > represent 1/3 exactly in either binary or decimal?)
I have written one, based on the work of Stephen L Moshier, in x86 asm 
and arm64 asm. It has aroud the same speed as GMP...
The layout is as follows:

Each number is 64 bytes, where the first 32 are the sign (I know is 
wasteful but it is faster than using only one bit) the, the next 32 are 
the exponent (biased) and then 7 64 bit integers with the mantissa.

All functions of the C standard library are provided using this format

[toc] | [prev] | [next] | [standalone]

#138516

jacob navia <jacob@jacob.remcomp.fr> writes:

> Le 04/12/2018 à 18:35, Bart a écrit :> An extended precision floating
> point library would also be intriguing to
>
>> write. But it can't be arbitrary precision. (How many digits to
>> represent 1/3 exactly in either binary or decimal?)
>
> I have written one, based on the work of Stephen L Moshier, in x86 asm
> and arm64 asm. It has aroud the same speed as GMP...  The layout is as
> follows:
>
> Each number is 64 bytes, where the first 32

bits

> are the sign (I know is
> wasteful but it is faster than using only one bit) the, the next 32

bits

> are the exponent (biased) and then 7 64 bit integers with the
> mantissa.

I was puzzled at first, so I thought it worth clarifying.

However, I'd call this extended precision rather than arbitrary
precision.  Please don't take this as a criticism.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#138517

On 04/12/2018 22:45, jacob navia wrote:
> Le 04/12/2018 à 18:35, Bart a écrit :> An extended precision floating 
> point library would also be intriguing to
>  > write. But it can't be arbitrary precision. (How many digits to
>  > represent 1/3 exactly in either binary or decimal?)
> I have written one, based on the work of Stephen L Moshier, in x86 asm 
> and arm64 asm. It has aroud the same speed as GMP...
> The layout is as follows:
> 
> Each number is 64 bytes, where the first 32 are the sign (I know is 
> wasteful but it is faster than using only one bit) the, the next 32 are 
> the exponent (biased) and then 7 64 bit integers with the mantissa.

So 32:32:448 bits totalling 512.

That explains the rather odd 448-bit size.

(The library I'm looking at wouldn't be a serious floating point 
implementation like this. Just a bit of fun at first, and rather 
experimental. And it would be unlimited precision (subject to practical 
matters), and most likely decimal, so it's not going to be fast.)

-- 
bart

[toc] | [prev] | [next] | [standalone]

#138560

On 12/4/2018 4:30 PM, Bart wrote:
> On 04/12/2018 22:45, jacob navia wrote:
>> Le 04/12/2018 à 18:35, Bart a écrit :> An extended precision floating 
>> point library would also be intriguing to
>>  > write. But it can't be arbitrary precision. (How many digits to
>>  > represent 1/3 exactly in either binary or decimal?)
>> I have written one, based on the work of Stephen L Moshier, in x86 asm 
>> and arm64 asm. It has aroud the same speed as GMP...
>> The layout is as follows:
>>
>> Each number is 64 bytes, where the first 32 are the sign (I know is 
>> wasteful but it is faster than using only one bit) the, the next 32 
>> are the exponent (biased) and then 7 64 bit integers with the mantissa.
> 
> So 32:32:448 bits totalling 512.
> 
> That explains the rather odd 448-bit size.
> 
> (The library I'm looking at wouldn't be a serious floating point 
> implementation like this. Just a bit of fun at first, and rather 
> experimental. And it would be unlimited precision (subject to practical 
> matters), and most likely decimal, so it's not going to be fast.)
> 

Fwiw, here is a library in JavaScript that I used in the past:

https://github.com/MikeMcl/decimal.js

It has the trigonometric functions I was looking for.

[toc] | [prev] | [next] | [standalone]

#138548

On Tue, 04 Dec 2018 23:45:56 +0100, jacob navia wrote:

> Each number is 64 bytes, where the first 32 are the sign (I know is
> wasteful but it is faster than using only one bit)

	That would not be wasteful - it would be crazy. One must assume 
you mean bits - which is wasteful indeed.

[toc] | [prev] | [next] | [standalone]

#138550

Le 05/12/2018 à 18:50, Jens Stuckelberger a écrit :
> On Tue, 04 Dec 2018 23:45:56 +0100, jacob navia wrote:
> 
>> Each number is 64 bytes, where the first 32 are the sign (I know is
>> wasteful but it is faster than using only one bit)
> 
> 	That would not be wasteful - it would be crazy. One must assume
> you mean bits - which is wasteful indeed.
> 

What is "wasteful"?

This is wasteful of space but spares time consuming masking operations.

Several options are available for the first 64 bits:

1: Sign 32 bits, biased exponent 32 bits. This is the one I use.
2: Sign 1 bit, biased exponent 31 bits, followed by 32 bits of data.
That would allow for fast tests for negative since the sign bit could be 
tested by testing for a negative 64 bit number, a single instruction.
Exponent access would be more involved since the sign bit must be masked
away. That would be fairly fast, but now the handling of the first 32 
bits would have to be special since all numbers are assumed base 2^64 
and the first would be base 2^32.
This could be done of course (just zero extend those 32 bits, but you 
would need intermediate storage for the first number... etc etc)

So, I decided to waste some space.

[toc] | [prev] | [next] | [standalone]

#138557

jacob navia <jacob@jacob.remcomp.fr> writes:
> Le 04/12/2018 à 18:35, Bart a écrit :
> > An extended precision floating 
> > point library would also be intriguing to
> > write. But it can't be arbitrary precision. (How many digits to
> > represent 1/3 exactly in either binary or decimal?)
> I have written one, based on the work of Stephen L Moshier, in x86 asm 
> and arm64 asm. It has aroud the same speed as GMP...
> The layout is as follows:
>
> Each number is 64 bytes, where the first 32 are the sign (I know is 
> wasteful but it is faster than using only one bit) the, the next 32 are 
> the exponent (biased) and then 7 64 bit integers with the mantissa.
>
> All functions of the C standard library are provided using this format

So you have a sign, a 32-bit exponent, and a 448-bit mantissa.

Unless I'm missing something, that still can't represent 1/3 exactly
(though it can approximate it much more closely than smaller formats
can).

To represent 1/3 *exactly*, you need either trinary (which
can't represent 1/5 or 1/7 exactly, or even 1/2) or some kind of
numerator/denominator representation.

-- 
Keith Thompson (The_Other_Keith) kst@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#138575

Le 05/12/2018 à 22:46, Keith Thompson a écrit :
> So you have a sign, a 32-bit exponent, and a 448-bit mantissa.
> 

yes

> Unless I'm missing something, that still can't represent 1/3 exactly
> (though it can approximate it much more closely than smaller formats
> can).
> 

For ANY base <n> there will be always some number that is not exactly 
representable in that base. For instance in base 10, 1/3 is

0.333333333...

Apparently for you this is a "bug" in my software or what?
Of course I can't represent 1/3 and I can't even less represent sqrt(2)
or pi!

> To represent 1/3*exactly*, you need either trinary (which
> can't represent 1/5 or 1/7 exactly, or even 1/2) or some kind of
> numerator/denominator representation.

The only way is to represent 1/3 as a numerator/denominator fraction. 
But that is easy since 1/3 is not an irrational number like sqrt(2), or 
even a trscendental number like pi or "e".

SO what?

My software runs in a computer and ALL computers can't represent 
irrational or trascendental numbers exactly

But you can't miss any occasion to keep silent. You HAVE to complain 
about my software. Apparently it is impossible to refrain yourself since 
already 10 or more years so I got used to it mr thompson. It just 
doesn't work any more.

[toc] | [prev] | [next] | [standalone]

#138576

jacobnavia <jacob@jacob.remcomp.fr> writes:
> Le 05/12/2018 à 22:46, Keith Thompson a écrit :
>> So you have a sign, a 32-bit exponent, and a 448-bit mantissa.
>
> yes
>
>> Unless I'm missing something, that still can't represent 1/3 exactly
>> (though it can approximate it much more closely than smaller formats
>> can).
>
> For ANY base <n> there will be always some number that is not exactly
> representable in that base. For instance in base 10, 1/3 is
>
> 0.333333333...
>
> Apparently for you this is a "bug" in my software or what?

No, not at all.  I was simply responding to your remarks upthread.

Bart wrote:
    An extended precision floating point library would also be
    intriguing to write. But it can't be arbitrary precision. (How many
    digits to represent 1/3 exactly in either binary or decimal?)

You replied:
    I have written one, based on the work of Stephen L Moshier, in x86
    asm and arm64 asm.

I took that as a claim that your system could represent 1/3 exactly.
Re-reading it, I see that you were probably responding to the
"extended precision" part of what Bart wrote, not to the "can't be
arbitrary precision" part.  As usual, I intended no personal attack.
(I understand that you don't believe that, but there's nothing I
can do about that.)

[snip]

-- 
Keith Thompson (The_Other_Keith) kst@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#138499

On Tuesday, December 4, 2018 at 7:18:09 AM UTC-5, Bart wrote:
> I've just put together a very simple such library, of the kind that I 
> might have used myself if it was available:
> 
>      https://github.com/sal55/mx/blob/master/bigint.h
>      https://github.com/sal55/mx/blob/master/bigint.c

If you would provide me a Public Domain license context, I'd like
to include your code in my projects.  It is simple and very easy
to understand.

Nicely done.

If you get a BigFloat library working too under the same Public
Domain license, I'd like to use it as well.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#138508

On 04/12/2018 17:08, Rick C. Hodgin wrote:
> On Tuesday, December 4, 2018 at 7:18:09 AM UTC-5, Bart wrote:
>> I've just put together a very simple such library, of the kind that I
>> might have used myself if it was available:
>>
>>       https://github.com/sal55/mx/blob/master/bigint.h
>>       https://github.com/sal55/mx/blob/master/bigint.c
> 
> If you would provide me a Public Domain license context, I'd like
> to include your code in my projects.  It is simple and very easy
> to understand.

OK, done. (Added a comment to that effect to the two source files.)

--
bart.

[toc] | [prev] | [next] | [standalone]

#138509

On Tuesday, December 4, 2018 at 2:41:27 PM UTC-5, Bart wrote:
> On 04/12/2018 17:08, Rick C. Hodgin wrote:
> > On Tuesday, December 4, 2018 at 7:18:09 AM UTC-5, Bart wrote:
> >> I've just put together a very simple such library, of the kind that I
> >> might have used myself if it was available:
> >>
> >>       https://github.com/sal55/mx/blob/master/bigint.h
> >>       https://github.com/sal55/mx/blob/master/bigint.c
> > 
> > If you would provide me a Public Domain license context, I'd like
> > to include your code in my projects.  It is simple and very easy
> > to understand.
> 
> OK, done. (Added a comment to that effect to the two source files.)

Thank you, Bart.  I admire the work you do.  Not just on this,
but generally across the board.  A few things make me scratch
my head, but on the whole ... I appreciate your efforts and
software.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#138616

On 04/12/2018 17:08, Rick C. Hodgin wrote:
> On Tuesday, December 4, 2018 at 7:18:09 AM UTC-5, Bart wrote:
>> I've just put together a very simple such library, of the kind that I
>> might have used myself if it was available:
>>
>>       https://github.com/sal55/mx/blob/master/bigint.h
>>       https://github.com/sal55/mx/blob/master/bigint.c
> 
> If you would provide me a Public Domain license context, I'd like
> to include your code in my projects.  It is simple and very easy
> to understand.
> 
> Nicely done.
> 
> If you get a BigFloat library working too under the same Public
> Domain license, I'd like to use it as well.
> 

I've started such a bigfloat library. Early days but I can't see why it 
can't do both floats and integers, without being that much longer or slower.

If so then it can do the job of the other library too. But I will likely 
change the interfaces to be more gmp-style, as that seems to work better:

     x = bn_init();

     bn_add(x,a,b);
     bn_mul(x,x,c);
     bn_sub(x,x,d);      // x=(a+b)*c+d

(where these functions can also return some useful value) instead of:

     x1 = bn_add(a,b);
     x2 = bn_mul(x1,c);
     x = bn_sub(x2,d);
     bn_free(x1);
     bn_free(x2);

This style will be kept in the original, but is more suited to embedded 
code where you wrap something else around it. Otherwise writing such 
code is a pain. (In the 40Kloc app where this library was used, bn_add() 
for example is only called twice, so it doesn't matter.)

[toc] | [prev] | [next] | [standalone]

#138521

On 05/12/2018 01:17, Bart wrote:
> 
> Bart [A modular build system for C]:
>   > Some people don't want to do that because they strongly object to
>   > having to run a 31,000-line bash script in a Linux emulation just to
>   > compile a C library. It is just crazy.
> 
> The complexities of building an arbitrary precision library like gmp
> were discussed recently.
> 
> I've just put together a very simple such library, of the kind that I
> might have used myself if it was available:
> 
>       https://github.com/sal55/mx/blob/master/bigint.h
>       https://github.com/sal55/mx/blob/master/bigint.c
> 
> This library, although providing the most basic functions and using the
> simplest algorithms, nevertheless ticks quite a few of my boxes:
> 
> * It's compactly presented as one module. (About 800 lines; just the
>     configure script for gmp is 30,000 lines, and in all gmp has over
>     1900 files in total, when you have to build from source.)
> 
> * Comes in a matching .h/.c pair, so would be compatible with the option
>     on my compiler that auto-locates the bodies of included headers:
> 
>       C:\c>bcc -auto main
>          1 Compiling main.c       to main.asm         (Pass 1)
>       *  2 Compiling bigint.c     to bigint.asm       (Pass 2)
>       Assembling to main.exe
> 
> * Keeps use of typedefs to a minimum (used to declare some aliases for
>     int32_t etc, and to make the one struct used, into a type)

Looks tidy, but I would keep those aliases out of the header - the _t 
names were partly picked to minimise the risk of name clashes.  Also 
they are slightly ironic coming from someone who decries C's plethora of 
types....

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#138526

On 05/12/2018 02:19, Ian Collins wrote:
> On 05/12/2018 01:17, Bart wrote:

>> * Keeps use of typedefs to a minimum (used to declare some aliases for
>>     int32_t etc, and to make the one struct used, into a type)
> 
> Looks tidy, but I would keep those aliases out of the header - the _t 
> names were partly picked to minimise the risk of name clashes. 

You mean, /I/ shouldn't use int32 so that someone else can?

> Also 
> they are slightly ironic coming from someone who decries C's plethora of 
> types....

It should have a list of types such that people shouldn't want to make 
up their own.

I will look at getting rid of both stdint.h and the typedefs, although 
the use of 'long long int' and 'unsigned int' will make things much less 
tidy.

[toc] | [prev] | [next] | [standalone]

#138532

On 05/12/18 12:58, Bart wrote:
> On 05/12/2018 02:19, Ian Collins wrote:
>> On 05/12/2018 01:17, Bart wrote:
> 
>>> * Keeps use of typedefs to a minimum (used to declare some aliases for
>>>     int32_t etc, and to make the one struct used, into a type)
>>
>> Looks tidy, but I would keep those aliases out of the header - the _t
>> names were partly picked to minimise the risk of name clashes. 
> 
> You mean, /I/ shouldn't use int32 so that someone else can?

You should not use "int32" in a /header/, in case other people want to
use it.  What you do in the /implementation/ is up to you.

To most of us, there is absolutely no point in having types like "int32"
as typedefs for "int32_t" - it is an entirely negative thing.  It merely
introduces a non-standard name with no functionality, severing to
confuse, complicate and irritate.  So /users/ of your library are not
remotely interested in having a type "int32" defined here.

I realise that you think "int32_t" is so hideously ugly that you don't
want to use it in your own code, and prefer a typedef to "int32".  I
can't say I can comprehend that attitude, but I can appreciate that this
is your opinion.  So if you want to use "int32" in your implementation
code, go ahead.  The emphasis in the C code should be what suits /you/
best, while the emphasis in the header file is what suits /others/ best.

I would actually severely question the choice of types here altogether.
 I would say more natural types would be :

typedef struct {
	uint_least32_t * ptr;
	unsigned int ndigits;
	bool minus;
} BigInt;

If you want C90 compatibility, use:

#if UINT_MAX < 0xffffffff
#error The implementation requires at least 32-bit unsigned int
#endif
typedef struct {
	unsigned int * ptr;
	unsigned int ndigits;
	int minus;
} BigInt;


As for the library itself, I have a few suggestions which you may or may
not use.  It is entirely up to you - it depends on how you want to use
the library.

First, in any API you should strive to minimise extra functions.
"bn_print" is useful - "bn_println" is not.

Secondly, be very careful to be clear about ownership of allocated
resources.  It is not clear from the functional API that BigInt types
hold resources and need freed by the user.  In particular, the "bn_free"
function is listed as paired with the "bn_tostring" function - it gives
the impression that you use "bn_free" to free the memory allocated by
the "bn_tostring" function, which is clearly not the case.

With a big number library, you have a choice of bases to use.  Base 10
makes printing easier - but it makes calculations a good deal less
efficient.  You have to choose which makes sense for you.  It is also
more common to use little-endian ordering - again, it is easier to be
efficient.

You could also separate the count of the blocks allocated from the
number of digits used.  This can make it easier to do in-place
operations (like "x += y") with fewer allocations and copies.  And you
really want in-place operations for a library like this:

	a = bn_add(a, b);

will be slow an leaky, while:

	bn_add_to(&a, b);

would be faster and safe.


Finally, I would want a "small number optimisation" feature - a fixed
size of data, perhaps 4 uint32_t or a single uint64_t - within the
BigInt struct itself.  Numbers that are small enough to be stored there
would be there, and be very much faster to use.

[toc] | [prev] | [next] | [standalone]

#138538

On 05/12/2018 13:35, David Brown wrote:
> On 05/12/18 12:58, Bart wrote:

>> You mean, /I/ shouldn't use int32 so that someone else can?
> 
> You should not use "int32" in a /header/, in case other people want to
> use it.  What you do in the /implementation/ is up to you.
> 
> To most of us, there is absolutely no point in having types like "int32"
> as typedefs for "int32_t" - it is an entirely negative thing.  It merely
> introduces a non-standard name with no functionality, severing to
> confuse, complicate and irritate.  So /users/ of your library are not
> remotely interested in having a type "int32" defined here.
> 
> I realise that you think "int32_t" is so hideously ugly that you don't
> want to use it in your own code, and prefer a typedef to "int32".  I
> can't say I can comprehend that attitude, but I can appreciate that this
> is your opinion.  So if you want to use "int32" in your implementation
> code, go ahead.  The emphasis in the C code should be what suits /you/
> best, while the emphasis in the header file is what suits /others/ best.
> 
> I would actually severely question the choice of types here altogether.

I think, because this seems to be a sore point, I will remove all such 
controversial matters from the header.

I might also change 'Bigint' to be an opaque pointer rather than a 
struct (and possibly using only an array rather than struct+array).

> First, in any API you should strive to minimise extra functions.
> "bn_print" is useful - "bn_println" is not.

(My test programs only use the latter! However here, the most general 
function is 'bn_tostring'.)

> You could also separate the count of the blocks allocated from the
> number of digits used.  This can make it easier to do in-place
> operations (like "x += y") with fewer allocations and copies.  And you
> really want in-place operations for a library like this:
> 
> 	a = bn_add(a, b);
> 
> will be slow an leaky, while:
> 
> 	bn_add_to(&a, b);
> 
> would be faster and safe.
> 
> 
> Finally, I would want a "small number optimisation" feature - a fixed
> size of data, perhaps 4 uint32_t or a single uint64_t - within the
> BigInt struct itself.  Numbers that are small enough to be stored there
> would be there, and be very much faster to use.

Thanks for the comments.

My own original requirement was for something to provide the underlying 
algorithms, and take care of all the fiddly work.

Those other things can either be built on top, or if the library is 
simple enough, it can be adapted. For example:

     void bn_add_to(Bigint* pa, Bigint b){
         Bigint c;
         c = bn_add(*pa, b);
         bn_free(*pa);
         *pa = c;
     }

While in the language where this was originally used, you can write this:

     a +:= b        # a, b both big integers

even though the underlying add routine has a similar interface to bn_add.

(Here, this isn't a true in-place addition. It is simulated like the 
bn_add_to example. One reason is that in this language when you do this:

    a := b

a and b will share the same numeric data. You don't want subsequent 
in-place changes to a to be reflected in b.)

[toc] | [prev] | [next] | [standalone]

#138542

On Wednesday, December 5, 2018 at 2:36:07 PM UTC, Bart wrote:
> 
> I might also change 'Bigint' to be an opaque pointer rather than a 
> struct (and possibly using only an array rather than struct+array).
> 
The snag with private data generally is that your design needs to be
perfect, because no calling programmer can ever patch it without
altering the original source file.

[toc] | [prev] | [next] | [standalone]

#138543

On Wednesday, December 5, 2018 at 1:39:19 PM UTC-2, Malcolm McLean wrote:
> On Wednesday, December 5, 2018 at 2:36:07 PM UTC, Bart wrote:
> > 
> > I might also change 'Bigint' to be an opaque pointer rather than a 
> > struct (and possibly using only an array rather than struct+array).
> > 
> The snag with private data generally is that your design needs to be
> perfect, because no calling programmer can ever patch it without
> altering the original source file.

The problem with opaque pointers is that you cannot 
allocate on stack.

[toc] | [prev] | [next] | [standalone]

Page 2 of 7 — ← Prev page 1 [2] 3 4 5 6 7  Next page →

Back to top | Article view | comp.lang.c

csiph-web