Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #138553
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Big integers |
| Date | 2018-12-05 22:15 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <pu9f58$gt0$1@dont-email.me> (permalink) |
| References | <YfuND.286973$lKb.275890@fx15.am4> <g6oqspF2giqU1@mid.individual.net> <L3PND.252067$Z%1.51148@fx16.am4> <pu8k6m$tva$1@dont-email.me> <inRND.427702$kh6.132887@fx32.am4> |
On 05/12/2018 15:35, 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.
Don't make changes because people here make complaints or suggestions.
/Read/ the complaints and suggestions, think about them, understanding
them, and then make an informed decision about what is best for the
software /you/ are writing. Obviously I think you should take my advice
and suggestions - but I want you to do it because you have understood
what I meant, and agree with me, and not just to shut me up!
>
> I might also change 'Bigint' to be an opaque pointer rather than a
> struct (and possibly using only an array rather than struct+array).
>
That is definitely something to consider. It is an unfortunate
limitation of C that some private information - such as the contents of
BigInt - need to be made visible in the header if you want local
allocation. When the details of the struct are in the header, users
might rely on them, making it more difficult to change the
implementation later. An opaque pointer type avoids that, but means
that everything has to be heap allocated in practice.
If you are doing that, you might want to have your BigInt something like:
typedef struct {
uint_least32_t dataAllocated;
uint_least32_t dataUsed;
bool minus;
uint_least32_t data[];
} BigInt;
That makes the data array a flexible array member. When you allocate a
new BigInt on the heap, add extra size to store the data. Keep track of
the allocated size in "dataAllocated" - then you know whether or not you
have space to grow a BigInt during a calculation. Typically you will
allocate with dataAllocated as 1 + 4*n, so that your resulting structure
is in 16-byte lumps - malloc() on x86 will generally give you memory
rounded up to 16-byte (or perhaps 32-byte) lumps.
This has the advantage that allocating and freeing a BigInt is just one
malloc and one free, avoiding the significant time and space overhead of
an extra allocation, and making freeing a BigInt as simple as calling
"free".
>> 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;
> }
Of course that is possible. But generally a "bn_add_to" function can be
much more efficient than an "bn_add" function, with fewer memory
accesses and no allocation or free (except if you are very unlucky with
the carry). You then use the bn_add_to function to implement bn_add,
not the other way around.
>
> 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.)
You need to be careful how you handle duplicates and references like
this. It is possible to use copy-on-write and other optimisations, but
then the code and interface gets more complex (and you'll wish you were
using C++ and not C).
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web