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 3 of 7 — ← Prev page 1 2 [3] 4 5 6 7  Next page →

#138549

Thiago Adams <thiago.adams@gmail.com> writes:

> 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.

Well...  You can do something like this:

  #define OPAQUE_TYPE_SIZE 32

  typedef struct {
      const char bytes[OPAQUE_TYPE_SIZE];
  } big_num;

in the public header.  This effectively prevents any fiddling with the
object but it's also probably against the rules.  I'd be surprised if a
compiler messed it up though.

You can even provide initialiser objects:

  extern big_num nm_zero, bn_one, bn_two;
  /* ... */
  big_num n = bn_one;

-- 
Ben.

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

#138555

On 05/12/2018 18:51, Ben Bacarisse wrote:
> Thiago Adams <thiago.adams@gmail.com> writes:
> 
>> 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.
> 
> Well...  You can do something like this:
> 
>    #define OPAQUE_TYPE_SIZE 32
> 
>    typedef struct {
>        const char bytes[OPAQUE_TYPE_SIZE];
>    } big_num;
> 
> in the public header.  This effectively prevents any fiddling with the
> object but it's also probably against the rules.  I'd be surprised if a
> compiler messed it up though.
> 

You might want to make this a union with a long long int, to improve 
alignment.

And if you have a powerful optimising compiler that might be tempted to 
optimise using type compatibility rules ("strict aliasing", in gcc 
terms), then you can use the __attribute__(("may_alias")) type attribute 
to help.

> You can even provide initialiser objects:
> 
>    extern big_num nm_zero, bn_one, bn_two;
>    /* ... */
>    big_num n = bn_one;
> 

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

#138562

On 12/5/2018 7:45 AM, Thiago Adams wrote:
> 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.
> 

Why not? There are different ways to do this.

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

#138565

On Wednesday, December 5, 2018 at 5:55:44 PM UTC-5, Chris M. Thomasson wrote:
> On 12/5/2018 7:45 AM, Thiago Adams wrote:
...
> > The problem with opaque pointers is that you cannot
> > allocate on stack.
> > 
> 
> Why not? There are different ways to do this.

Could you give an example?

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

#138569

On 12/5/2018 3:19 PM, jameskuyper@alumni.caltech.edu wrote:
> On Wednesday, December 5, 2018 at 5:55:44 PM UTC-5, Chris M. Thomasson wrote:
>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
> ...
>>> The problem with opaque pointers is that you cannot
>>> allocate on stack.
>>>
>>
>> Why not? There are different ways to do this.
> 
> Could you give an example?
> 

User creates a region allocator R on the stack.

User passes a pointer to R, to an API "factory function" that outputs a 
pointer to a memory residing in R sufficient to hold the request, or 
returns NULL.

If the output is not NULL, the pointer returned by the API resides on 
the stack of the caller within R, ready to be used by further calls to 
said API.

If the API function returns NULL because R is "full", the user can try 
again using a flag for the API to use dynamic memory...

Fin.

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

#138577

On 06/12/18 01:13, Chris M. Thomasson wrote:
> On 12/5/2018 3:19 PM, jameskuyper@alumni.caltech.edu wrote:
>> On Wednesday, December 5, 2018 at 5:55:44 PM UTC-5, Chris M. Thomasson
>> wrote:
>>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>> ...
>>>> The problem with opaque pointers is that you cannot
>>>> allocate on stack.
>>>>
>>>
>>> Why not? There are different ways to do this.
>>
>> Could you give an example?
>>
> 
> User creates a region allocator R on the stack.
> 
> User passes a pointer to R, to an API "factory function" that outputs a
> pointer to a memory residing in R sufficient to hold the request, or
> returns NULL.
> 
> If the output is not NULL, the pointer returned by the API resides on
> the stack of the caller within R, ready to be used by further calls to
> said API.
> 
> If the API function returns NULL because R is "full", the user can try
> again using a flag for the API to use dynamic memory...
> 
> Fin.

That sounds really messy and complicated - re-implementing malloc/free
in your big number library.  But it would be possible to have a macro
that allocated the required amount of memory on the stack, using
alloca() or a VLA, and passed a pointer to the "factory function".  This
would simply initialise the structure at the given address, and return
the pointer, cast to the correct type.

Still, it would be ugly, and would work poorly if you need to allocate
and free regularly during calculations (as is needed in Bart's library).

If you want to store things on stack, then splitting the structure into
a fixed basic object and a dynamic data block makes more sense.  Give
the basic object enough space to be able to handle common cases
efficiently (such as a 64-bit integer in this case).

Of preference, use C++ - that way the language can handle your
allocation and deallocation automatically, and make life much easier for
the users.

And just accept that in C and C++, you have to put some of the private
implementation information in the public headers, if you want to avoid
inefficiencies and complications.

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

#138610

On 12/6/2018 12:35 AM, David Brown wrote:
> On 06/12/18 01:13, Chris M. Thomasson wrote:
>> On 12/5/2018 3:19 PM, jameskuyper@alumni.caltech.edu wrote:
>>> On Wednesday, December 5, 2018 at 5:55:44 PM UTC-5, Chris M. Thomasson
>>> wrote:
>>>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>>> ...
>>>>> The problem with opaque pointers is that you cannot
>>>>> allocate on stack.
>>>>>
>>>>
>>>> Why not? There are different ways to do this.
>>>
>>> Could you give an example?
>>>
>>
>> User creates a region allocator R on the stack.
>>
>> User passes a pointer to R, to an API "factory function" that outputs a
>> pointer to a memory residing in R sufficient to hold the request, or
>> returns NULL.
>>
>> If the output is not NULL, the pointer returned by the API resides on
>> the stack of the caller within R, ready to be used by further calls to
>> said API.
>>
>> If the API function returns NULL because R is "full", the user can try
>> again using a flag for the API to use dynamic memory...
>>
>> Fin.
> 
> That sounds really messy and complicated - re-implementing malloc/free
> in your big number library.  

Yeah, its not pretty.


> But it would be possible to have a macro
> that allocated the required amount of memory on the stack, using
> alloca() or a VLA, and passed a pointer to the "factory function".  This
> would simply initialise the structure at the given address, and return
> the pointer, cast to the correct type.

That should work as well.


> Still, it would be ugly, and would work poorly if you need to allocate
> and free regularly during calculations (as is needed in Bart's library).

Agreed. One would basically have to create their own little memory 
management scheme to work on the stack.


> If you want to store things on stack, then splitting the structure into
> a fixed basic object and a dynamic data block makes more sense.  Give
> the basic object enough space to be able to handle common cases
> efficiently (such as a 64-bit integer in this case).
> 
> Of preference, use C++ - that way the language can handle your
> allocation and deallocation automatically, and make life much easier for
> the users.
> 
> And just accept that in C and C++, you have to put some of the private
> implementation information in the public headers, if you want to avoid
> inefficiencies and complications.

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

#138614

On 12/7/2018 2:26 PM, Chris M. Thomasson wrote:
> On 12/6/2018 12:35 AM, David Brown wrote:
>> On 06/12/18 01:13, Chris M. Thomasson wrote:
>>> On 12/5/2018 3:19 PM, jameskuyper@alumni.caltech.edu wrote:
>>>> On Wednesday, December 5, 2018 at 5:55:44 PM UTC-5, Chris M. Thomasson
>>>> wrote:
>>>>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>>>> ...
>>>>>> The problem with opaque pointers is that you cannot
>>>>>> allocate on stack.
>>>>>>
>>>>>
>>>>> Why not? There are different ways to do this.
>>>>
>>>> Could you give an example?
>>>>
>>>
>>> User creates a region allocator R on the stack.
>>>
>>> User passes a pointer to R, to an API "factory function" that outputs a
>>> pointer to a memory residing in R sufficient to hold the request, or
>>> returns NULL.
>>>
>>> If the output is not NULL, the pointer returned by the API resides on
>>> the stack of the caller within R, ready to be used by further calls to
>>> said API.
>>>
>>> If the API function returns NULL because R is "full", the user can try
>>> again using a flag for the API to use dynamic memory...
>>>
>>> Fin.
>>
>> That sounds really messy and complicated - re-implementing malloc/free
>> in your big number library. 
> 
> Yeah, its not pretty.
[...]

However, it can be nice if the region allocator had all the stack memory 
the API needed to perform the calculation without resorting to dynamic 
memory. Lets say 80% of the calcs were using on stack memory...

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

#138629

On 12/5/18 17:55, Chris M. Thomasson wrote:
> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>> 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.
>>
> 
> Why not? There are different ways to do this.
While the C standard never refers to a "stack" in any way,
implementations targeting platforms which have a stack conventionally
use it for objects with automatic storage duration. The reason why a
stack is convenient for that purpose is that an object with automatic
storage duration has a lifetime that ends when the function in which
it's defined in terminated. In this context, this means that the
function where the object with automatic storage duration is defined
must never terminate until all use of that memory is over - all other
routines that make use of that memory must therefore be direct or
indirect subroutines of that functions. While there are, as you say,
"many different ways to do this", they're all rather tricky or clumsy.

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

#138653

On 12/9/2018 9:01 AM, James Kuyper wrote:
> On 12/5/18 17:55, Chris M. Thomasson wrote:
>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>>> 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.
>>>
>>
>> Why not? There are different ways to do this.
> While the C standard never refers to a "stack" in any way,
> implementations targeting platforms which have a stack conventionally
> use it for objects with automatic storage duration. The reason why a
> stack is convenient for that purpose is that an object with automatic
> storage duration has a lifetime that ends when the function in which
> it's defined in terminated. In this context, this means that the
> function where the object with automatic storage duration is defined
> must never terminate until all use of that memory is over - all other
> routines that make use of that memory must therefore be direct or
> indirect subroutines of that functions. While there are, as you say,
> "many different ways to do this", they're all rather tricky or clumsy.
> 

A while back, I created a multi-threaded allocator that did not use 
dynamic memory. It could even allocate in thread A, and free in thread 
N. Never calling malloc or free.

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

#138655

"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> writes:
>On 12/9/2018 9:01 AM, James Kuyper wrote:
>> On 12/5/18 17:55, Chris M. Thomasson wrote:
>>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>>>> 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.
>>>>
>>>
>>> Why not? There are different ways to do this.
>> While the C standard never refers to a "stack" in any way,
>> implementations targeting platforms which have a stack conventionally
>> use it for objects with automatic storage duration. The reason why a
>> stack is convenient for that purpose is that an object with automatic
>> storage duration has a lifetime that ends when the function in which
>> it's defined in terminated. In this context, this means that the
>> function where the object with automatic storage duration is defined
>> must never terminate until all use of that memory is over - all other
>> routines that make use of that memory must therefore be direct or
>> indirect subroutines of that functions. While there are, as you say,
>> "many different ways to do this", they're all rather tricky or clumsy.
>> 
>
>A while back, I created a multi-threaded allocator that did not use 
>dynamic memory. It could even allocate in thread A, and free in thread 
>N. Never calling malloc or free.

A common property of any thread-safe pool allocator.

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

#138656

On 12/10/2018 4:50 PM, Scott Lurndal wrote:
> "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> writes:
>> On 12/9/2018 9:01 AM, James Kuyper wrote:
>>> On 12/5/18 17:55, Chris M. Thomasson wrote:
>>>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>>>>> 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.
>>>>>
>>>>
>>>> Why not? There are different ways to do this.
>>> While the C standard never refers to a "stack" in any way,
>>> implementations targeting platforms which have a stack conventionally
>>> use it for objects with automatic storage duration. The reason why a
>>> stack is convenient for that purpose is that an object with automatic
>>> storage duration has a lifetime that ends when the function in which
>>> it's defined in terminated. In this context, this means that the
>>> function where the object with automatic storage duration is defined
>>> must never terminate until all use of that memory is over - all other
>>> routines that make use of that memory must therefore be direct or
>>> indirect subroutines of that functions. While there are, as you say,
>>> "many different ways to do this", they're all rather tricky or clumsy.
>>>
>>
>> A while back, I created a multi-threaded allocator that did not use
>> dynamic memory. It could even allocate in thread A, and free in thread
>> N. Never calling malloc or free.
> 
> A common property of any thread-safe pool allocator.
> 

It was indeed a per-thread pool/region allocator setup that allowed a 
remote thread to free. The memory was located on the threads stacks.

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

#138694

On 12/10/2018 5:37 PM, Chris M. Thomasson wrote:
> On 12/10/2018 4:50 PM, Scott Lurndal wrote:
>> "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> writes:
>>> On 12/9/2018 9:01 AM, James Kuyper wrote:
>>>> On 12/5/18 17:55, Chris M. Thomasson wrote:
>>>>> On 12/5/2018 7:45 AM, Thiago Adams wrote:
>>>>>> 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.
>>>>>>
>>>>>
>>>>> Why not? There are different ways to do this.
>>>> While the C standard never refers to a "stack" in any way,
>>>> implementations targeting platforms which have a stack conventionally
>>>> use it for objects with automatic storage duration. The reason why a
>>>> stack is convenient for that purpose is that an object with automatic
>>>> storage duration has a lifetime that ends when the function in which
>>>> it's defined in terminated. In this context, this means that the
>>>> function where the object with automatic storage duration is defined
>>>> must never terminate until all use of that memory is over - all other
>>>> routines that make use of that memory must therefore be direct or
>>>> indirect subroutines of that functions. While there are, as you say,
>>>> "many different ways to do this", they're all rather tricky or clumsy.
>>>>
>>>
>>> A while back, I created a multi-threaded allocator that did not use
>>> dynamic memory. It could even allocate in thread A, and free in thread
>>> N. Never calling malloc or free.
>>
>> A common property of any thread-safe pool allocator.
>>
> 
> It was indeed a per-thread pool/region allocator setup that allowed a 
> remote thread to free. The memory was located on the threads stacks.

A thread was not allowed to exit until all outstanding memory was 
rendered into a quiescent state. Should do an impl of it again for fun. 
The problem, is that if I did it in C11, who would be able to compile 
it? Pelles users aside for a moment...

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

#138544

On Wednesday, December 5, 2018 at 12:36:07 PM UTC-2, Bart wrote:
> 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).


I would like to see something semantically similar of
new JavaScript BigInt. Because learning one you learn
the other and someone else (lot of people) is documenting 
and checking the design.

https://tc39.github.io/proposal-bigint/#sec-ecmascript-language-types-bigint-type


I also wold like to find a DOMParser semantically similar 
of html5 and with single c file .

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

#138545

On 05/12/2018 14:35, Bart wrote:

> 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).

I've changed the types used completely. Updated sources via links in OP. 
No more stdint.h either (I never liked having to include that file).

(Some more testing needed; in particular, bn_ineg/bn_iabs have had an 
indirection level removed, but it needs to go back in I think.)

Instead of a struct, the Bigint type is just a int*, although normally 
opaque to programs.

This uses an allocated array of N+2 elements, but a Bigint points to 
element [2], the data, while elements [0] and [1] store length/sign info.

I don't know if such a practice is frowned upon, but that's what I'm 
using. (This offset is not essential, but it means array data ops are 
always over 0..N-1 instead of 2..N+1.)


The new code requires int to be 32 bits or more, and long long int to be 
64 bits or more. (But it could be more easily adapted to 16-bit targets.)




-- 
bart

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

#138563

On 05/12/2018 15:59, Bart wrote:
> On 05/12/2018 14:35, Bart wrote:
> 
>> 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).
> 
> I've changed the types used completely. Updated sources via links in OP. 
> No more stdint.h either (I never liked having to include that file).
> 
> (Some more testing needed;

I've made some tweaks, and tested on 100 random numbers and random 
binary ops up to 10K digits, and 100,000 combinations up to 1K digits. 
Comparisons were made with Python 3.4 using its built-in [binary] 
arithmetic.

However, I had to use only positive numbers, because Python gives weird 
results when dividing negative ones (// is integer division):

   -10 // 20  is apparently -1, not 0.
   -30 // 20  is 2, not 1

These seem rather perverse, but I remember C having this problem (?).

Otherwise, results matched exactly. The only problem that come up was 
that multiplying with 0 gave lots of leading zeros, which was fixed.

(Speed wasn't that bad either compared with Python (which uses very fast 
internal routines), provided I used gcc to compile, as it can do some 
very good optimisations. However on longer numbers my library will get 
much slower, as it uses school long multiplication and division.)

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

#138566

On Wednesday, December 5, 2018 at 5:59:39 PM UTC-5, Bart wrote:
...
> However, I had to use only positive numbers, because Python gives weird 
> results when dividing negative ones (// is integer division):
> 
>    -10 // 20  is apparently -1, not 0.
>    -30 // 20  is 2, not 1
> 
> These seem rather perverse, but I remember C having this problem (?).

C originally allowed -10/20 to be either -1 or 0: the relevant rules are
called "round toward negative infinity" or "round toward 0". In C99, the
rules were changed to mandate 0. Your results imply that Python made the
opposite choice.

In my own personal experience, when I've cared about the results of
division with mixed signs, I've almost always wanted "round toward
negative infinity". A plot of x/N for fixed N using C's rule shows a
jump near x==0 that is NOT what I would want to see. C defines x%N in a
way that ties it directly to x/N, and C's rule very definitely does not
give me what I usually want for x%N when x and N have different signs.
However, it's better to have one consistent rule, even if it's the wrong
rule from my point of view, than to leave it unspecified.

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

#138572

On Wed, 5 Dec 2018 15:31:19 -0800 (PST),
jameskuyper@alumni.caltech.edu wrote:

>On Wednesday, December 5, 2018 at 5:59:39 PM UTC-5, Bart wrote:
>...
>> However, I had to use only positive numbers, because Python gives weird 
>> results when dividing negative ones (// is integer division):
>> 
>>    -10 // 20  is apparently -1, not 0.
>>    -30 // 20  is 2, not 1
>> 
>> These seem rather perverse, but I remember C having this problem (?).
>
>C originally allowed -10/20 to be either -1 or 0: the relevant rules are
>called "round toward negative infinity" or "round toward 0". In C99, the
>rules were changed to mandate 0. Your results imply that Python made the
>opposite choice.
>
>In my own personal experience, when I've cared about the results of
>division with mixed signs, I've almost always wanted "round toward
>negative infinity". A plot of x/N for fixed N using C's rule shows a
>jump near x==0 that is NOT what I would want to see. C defines x%N in a
>way that ties it directly to x/N, and C's rule very definitely does not
>give me what I usually want for x%N when x and N have different signs.
>However, it's better to have one consistent rule, even if it's the wrong
>rule from my point of view, than to leave it unspecified.


It's definitely application dependent, and I've wanted it both ways,
sometimes in the same program.  If you're dealing with graphics around
an axis, you get a nasty discontinuity unless you have
round-to-minus-infinity.  If you're dealing with currency, or in many
cases counts of things, you almost always want round-to-zero (unless
you want "proper" rounding - "round-to-nearest", for example).  The
Forth guys gave up trying to decide, and provide both operations in
the standard.

The direction of rounding also impacts the sign of the remainder.

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

#138567

Bart <bc@freeuk.com> writes:
>On 05/12/2018 15:59, Bart wrote:
>> On 05/12/2018 14:35, Bart wrote:

>However, I had to use only positive numbers, because Python gives weird 
>results when dividing negative ones (// is integer division):
>
>   -10 // 20  is apparently -1, not 0.
>   -30 // 20  is 2, not 1


 See, for example, the C function 'round':

$ man round
...
DESCRIPTION
       These  functions round x to the nearest integer, but round halfway cases away from
       zero (regardless of the current rounding direction, see fenv(3)), instead of
       to the nearest even integer like rint(3).

       For example, round(0.5) is 1.0, and round(-0.5) is -1.0.

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

#138571

On 12/5/18 18:42, Scott Lurndal wrote:
> Bart <bc@freeuk.com> writes:
>> On 05/12/2018 15:59, Bart wrote:
>>> On 05/12/2018 14:35, Bart wrote:
> 
>> However, I had to use only positive numbers, because Python gives weird 
>> results when dividing negative ones (// is integer division):
>>
>>   -10 // 20  is apparently -1, not 0.
>>   -30 // 20  is 2, not 1
> 
> 
>  See, for example, the C function 'round':
> 
> $ man round
> ...
> DESCRIPTION
>        These  functions round x to the nearest integer, but round halfway cases away from
>        zero (regardless of the current rounding direction, see fenv(3)), instead of
>        to the nearest even integer like rint(3).
> 
>        For example, round(0.5) is 1.0, and round(-0.5) is -1.0.

That's only for floating point rounding - and notice that the C standard
provides a variety of different rounding functions, which differ in how
they deal with the rounding direction: ceil(), floor(), nearbyint(),
rint(), round(), and trunc().

The rule for integer division doesn't involve a special case for the
half-way point. -19/20 and -1/20 are both 0 under the current rules, and
both of them were permitted to be -1 under the C90 rules.

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

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

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

csiph-web