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

#138619

On 08/12/2018 14:15, David Brown wrote:
> On 08/12/2018 15:13, David Brown wrote:

>> Bart's latest thoughts of using an interface style "bm_add(x, a, b);" 
>> rather than "x = bm_add(a, b);" is a good one, and it opens for the 
>> idea of a status return if that suits his needs.
>>
> 
> Another possibility (which occurred to me after pressing "send") is that 
> the BigInt struct currently has a 32-bit field for the "minus" flag. 
> This could contain other flags, such as a "NaN" or "error" flag, with as 
> many other details (infinities, overflow, underflow, etc.) as desired.
> 

That was last week...

The new library will do some of that, as it's for floating point and 
needs a few extra bits. It also needs a 2-level data structure (pointer 
to struct containing pointer to data) to support the new passing method.

(Very early version here, missing out the binary ops: (not in C, despite 
the extension, which was used to give it some colour): 
https://github.com/sal55/mx/blob/master/bigreal.c. It'll be hand-ported 
to actual C when done.)

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

#138640

On Saturday, December 8, 2018 at 12:48:53 PM UTC-2, Bart wrote:
...
>The new library will do some of that, as it's for floating point and 
> needs a few extra bits. 

Who needs bigreal? I don't know any usage.

To do math what is necessary is symbolic math. At the 
end you can ask the answer in a numeric form and then
you can compute using more and more decimal places. Just
at the end and not during the computation. So I don't any
application for big float points. Maybe a fixed 128 and thats it.

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

#138641

On Monday, December 10, 2018 at 1:10:43 PM UTC, Thiago Adams wrote:
> On Saturday, December 8, 2018 at 12:48:53 PM UTC-2, Bart wrote:
> ...
> >The new library will do some of that, as it's for floating point and 
> > needs a few extra bits. 
> 
> Who needs bigreal? I don't know any usage.
> 
> To do math what is necessary is symbolic math. At the 
> end you can ask the answer in a numeric form and then
> you can compute using more and more decimal places. Just
> at the end and not during the computation. So I don't any
> application for big float points. Maybe a fixed 128 and thats it.
>
Big reals are useful in graphics algorithms for resolving the degenerate/
near degenerate problem. For example you are asked to solve the intersection
of two lines which share an endpoint calculated in two mathematically
equivalent ways, but with slightly different floating point results.

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

#138642

On 10/12/18 14:22, Malcolm McLean wrote:
> On Monday, December 10, 2018 at 1:10:43 PM UTC, Thiago Adams wrote:
>> On Saturday, December 8, 2018 at 12:48:53 PM UTC-2, Bart wrote:
>> ...
>>> The new library will do some of that, as it's for floating point and 
>>> needs a few extra bits. 
>>
>> Who needs bigreal? I don't know any usage.
>>
>> To do math what is necessary is symbolic math. At the 
>> end you can ask the answer in a numeric form and then
>> you can compute using more and more decimal places. Just
>> at the end and not during the computation. So I don't any
>> application for big float points. Maybe a fixed 128 and thats it.

I too am curious about the applications.  This is not really my field,
and I am interested to hear about use-cases.

For very large integer stuff, I know of two main types of use.  One is
for encryption work.  In those cases, you generally have a fixed known
size for the numbers you are using - that would allow you some
conveniences compared to dynamic sizing, but I expect the efficiency
gains would be fairly small in practice.

The other use is in number theory mathematics, combinatorics, etc.

For floating point, quad precision (128-bit) is available in hardware on
a couple of devices, and octal precision is defined as an IEEE format.
I expect that for some kinds of numerical calculation, more than double
precision can be useful - such as for working with large matrices or
polynomials where you can often be mixing values over a very large
dynamic range.

But I don't know of any uses of arbitrary precision floating point data,
except perhaps for some mathematical curiosities.  And of course, there
is the fun of writing such libraries!

>>
> Big reals are useful in graphics algorithms for resolving the degenerate/
> near degenerate problem. For example you are asked to solve the intersection
> of two lines which share an endpoint calculated in two mathematically
> equivalent ways, but with slightly different floating point results.
> 

Graphics algorithms are more likely to use very short types, not very
long ones.

And the intersection of two lines which share an endpoint is that
endpoint (unless the lines are coincident).

So I think you'll have to explain that one a little better if it is to
make sense.

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

#138644

David Brown <david.brown@hesbynett.no> writes:
>On 10/12/18 14:22, Malcolm McLean wrote:

>> Big reals are useful in graphics algorithms for resolving the degenerate/
>> near degenerate problem. For example you are asked to solve the intersection
>> of two lines which share an endpoint calculated in two mathematically
>> equivalent ways, but with slightly different floating point results.
>> 
>
>Graphics algorithms are more likely to use very short types, not very
>long ones.

Indeed, hence the addition of 16-bit floating point types on
various mainstream processors (generally in the context of the
SIMD instruction set).    Heavily used in ML and AI applications
as well.

Note that with larger native FP types, memory bandwidth starts to become
a bottleneck.

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

#138678

David Brown <david.brown@hesbynett.no> wrote:
> On 10/12/18 14:22, Malcolm McLean wrote:
> > On Monday, December 10, 2018 at 1:10:43 PM UTC, Thiago Adams wrote:
> >> On Saturday, December 8, 2018 at 12:48:53 PM UTC-2, Bart wrote:
> >> ...
> >>> The new library will do some of that, as it's for floating point and 
> >>> needs a few extra bits. 
> >>
> >> Who needs bigreal? I don't know any usage.
> >>
> >> To do math what is necessary is symbolic math. At the 
> >> end you can ask the answer in a numeric form and then
> >> you can compute using more and more decimal places. Just
> >> at the end and not during the computation. So I don't any
> >> application for big float points. Maybe a fixed 128 and thats it.
> 
> I too am curious about the applications.  This is not really my field,
> and I am interested to hear about use-cases.
> 
> For very large integer stuff, I know of two main types of use.  One is
> for encryption work.  In those cases, you generally have a fixed known
> size for the numbers you are using - that would allow you some
> conveniences compared to dynamic sizing, but I expect the efficiency
> gains would be fairly small in practice.
> 
> The other use is in number theory mathematics, combinatorics, etc.

I would call this "symbolic computations".  For example, you want
formula for an integral or solution to a differential equation.
It is well-known that if you do symbolic computations using simple
algorithms you will get numbers of enormous size in intermediate
calculations even if initial data is small and the final result is
small.

For integers I find useful disitinction of into 3 kinds:
- Sligtly larger than machine words (say up to 10 machine words).
  For them fixed alocation of maximal size frequently is a
  big win, otherwise memory management may take more time
  than calculations
- Medium sized ones.  Here dynamic allocation frequently is
  only reasonable choice, while arithmetic can use naive
  algorithms but needs attention to low level details
  (usually special purpose assembler code) to get good
  speed.
- Large ones, where you wish good algorithms.

Small and medium sized bignums are very frequent in symbolic
computations.  When large bignum appear during calculations
people frequently spend considerable effort to rearrange
calculations so that smaller numbers are sufficient, but
sometimes such attempts fail.  Also, in symbolic computations
one frequently deals with polynomials.  There are tricks
to pack a polynomial with with moderately sized coefficients
into much larger integer (the integer must be large enough
to store all coefficients of the polynomial).  Then you
perform operation on integers and from result get back
a polynomial.  Some operations on polynomials can be
done faster that way (compared to working directly
with polynomials).
> 
> For floating point, quad precision (128-bit) is available in hardware on
> a couple of devices, and octal precision is defined as an IEEE format.
> I expect that for some kinds of numerical calculation, more than double
> precision can be useful - such as for working with large matrices or
> polynomials where you can often be mixing values over a very large
> dynamic range.
> 
> But I don't know of any uses of arbitrary precision floating point data,
> except perhaps for some mathematical curiosities.  And of course, there
> is the fun of writing such libraries!

You call that curiosities but symbolic results can be useful to
engineers.  For some integer functions the fastest method to
compute them involves floating point.  If error of floating
point computation is smaller than 1/2 you can round floating
point result to nearest integer and recover _exact_ integer
result.  But to make sure that error is smaller than 1/2 you
may need say 10000000 digits in intermedate calculations.

For relatively small big floats there is another use.  Namely
some useful formulas (like inverse Laplace transform) are very
unstable numerically.  You may need 50-100 digits in intermedate
calculations to get few digits of final precision.  But
despite slowness of software big floats the computation may
still be faster than alternatives.  And if money is involved
(like in geological search) more accurate result may be well
worth extra compute time.

> >>
> > Big reals are useful in graphics algorithms for resolving the degenerate/
> > near degenerate problem. For example you are asked to solve the intersection
> > of two lines which share an endpoint calculated in two mathematically
> > equivalent ways, but with slightly different floating point results.
> > 
> 
> Graphics algorithms are more likely to use very short types, not very
> long ones.
> 
> And the intersection of two lines which share an endpoint is that
> endpoint (unless the lines are coincident).
> 
> So I think you'll have to explain that one a little better if it is to
> make sense.

There is well-known problem of determining visibility, basically
you need to know which side of triangle is visible.  Getting this
wrong can produce visible artifacts.  Worse, getting inconsistent
results for several triangles can produce completely different
configuration than intended.  Standard test compute determinat
of 3 by 3 matrix and look at sign.  16-bit integers need about 50-bits
of accuracy to get correct sign.  Doable using machine doubles.
But little inattention like using float or some shifts which
enlarge integers by just few bits may lead to wrong results.

Probably more relevant to CAD, where dimensions may need more than
16bit for accurate representation and wrong configuration can
lead to non-working product (surface with hole or parts that
crash during movement).

-- 
                              Waldek Hebisch

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

#138643

On 10/12/2018 13:10, Thiago Adams wrote:
> On Saturday, December 8, 2018 at 12:48:53 PM UTC-2, Bart wrote:
> ...
>> The new library will do some of that, as it's for floating point and
>> needs a few extra bits.
> 
> Who needs bigreal? I don't know any usage.
> 
> To do math what is necessary is symbolic math. At the
> end you can ask the answer in a numeric form and then
> you can compute using more and more decimal places. Just
> at the end and not during the computation. So I don't any
> application for big float points. Maybe a fixed 128 and thats it.


That's something different. Apparently some people think it is relevant, 
as there are quite a few libraries for it; see the entries for floating 
point arithmetic here:

 
https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software

I've never used arbitrary precision floating point, but I could have 
done with it a few times, to get away from the restrictions of a mere 52 
/binary/ bits of precision, and the 1e-308/1e+308 range, and the 
difficulties of printing an accurate representation of even those 52 
bits (some printf implementations are reluctant to get anywhere near).

My version will be arbitrary precision /decimal/ floating point. 
(Division and some maths functions will need to use a pre-set precision, 
but it can be anything.)

And (I don't know if this is unusual) it can be used as an integer 
library too. Theoretical maximum precision is in the billions of digits 
(in practice, probably 1 million for add/subtract, somewhat less for 
multiply/divide, otherwise you will wait too long for results).

If I create the number A as "1e-100000000" and print it to a file, the 
file will be 100MB and contain "0.00000000 .... 0000001".

If I add 1 to A, and write the result, I get another 100MB file  containing:

         "1.000000000 ... 00000001"

That final 1 digit is still significant! So apart from anything else, 
this is fun.

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

#138645

On 2018-12-10, Bart <bc@freeuk.com> wrote:
> If I create the number A as "1e-100000000" and print it to a file, the 
> file will be 100MB and contain "0.00000000 .... 0000001".
>
> If I add 1 to A, and write the result, I get another 100MB file  containing:
>
>          "1.000000000 ... 00000001"
>
> That final 1 digit is still significant! So apart from anything else, 
> this is fun.

What will be the size of the result if A is divided by three?

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

#138646

On 10/12/2018 17:46, Ike Naar wrote:
> On 2018-12-10, Bart <bc@freeuk.com> wrote:
>> If I create the number A as "1e-100000000" and print it to a file, the
>> file will be 100MB and contain "0.00000000 .... 0000001".
>>
>> If I add 1 to A, and write the result, I get another 100MB file  containing:
>>
>>           "1.000000000 ... 00000001"
>>
>> That final 1 digit is still significant! So apart from anything else,
>> this is fun.
> 
> What will be the size of the result if A is divided by three?
> 

Here's a bit you snipped:

  "(Division and some maths functions will need to use a pre-set
   precision, but it can be anything.)"

How does it work with other such libraries?

How does it work with pencil and paper calculations (for something you 
don't already know)?

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

#138649

On Monday, December 10, 2018 at 4:24:30 PM UTC-2, Bart wrote:
> On 10/12/2018 17:46, Ike Naar wrote:
> > On 2018-12-10, Bart  wrote:
> >> If I create the number A as "1e-100000000" and print it to a file, the
> >> file will be 100MB and contain "0.00000000 .... 0000001".
> >>
> >> If I add 1 to A, and write the result, I get another 100MB file  containing:
> >>
> >>           "1.000000000 ... 00000001"
> >>
> >> That final 1 digit is still significant! So apart from anything else,
> >> this is fun.
> > 
> > What will be the size of the result if A is divided by three?
> > 
> 
> Here's a bit you snipped:
> 
>   "(Division and some maths functions will need to use a pre-set
>    precision, but it can be anything.)"
> 
> How does it work with other such libraries?
> 
> How does it work with pencil and paper calculations (for something you 
> don't already know)?


Using "paper"

1.00..001 is the same of

100..001
--------
100..000

divided by 3 is the same of:

100..001    1
-------- * ---
100..000    3

that is:

100..001
--------
300..000

To do math like in the paper, we need symbolic math.
You need to have more types. You need
a type for fractions (you can use bigint
for numerator and denominator).

You also need symbols to represent some numbers
like pi and e etc. square roots will be represented
by symbols as well.

Then at the end, after computation you will have some
expression. Now you can see the value as number.

For instance:

PI * 2. I want to see this result with 100 digits.
First you need to produce 100 digits of pi and then
multiply for 2.  The same for sqrt(5) * 2 

I have implemented many  years ago a symbolic math
evaluator.  I used to keep the expressions as RPN form.

PI 2 *


Other operations like sin, cos is the same.
I think is possible to find algorithm to generate 
sin for N digits using fraction. For instance using 
series.

For instance sin(x) is the same of

    x^3    x^5
x-  --- + ----  .. (Maclaurin Expansion of sin(x))
     3!     5!

then using bigint we can compute sin(10) for instance
with many digits using this serie.

sin(PI) will be necessary other method.

So this is really interesting in my opinion
much more than big real.

Some algorithms like Gaussian  elimination can be used
with symbolic math. So it is interesting to carry the symbols
and see the result at the end.
During the process of we need to simplify the expression
to avoid giant results as well.

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

#138650

On Monday, December 10, 2018 at 5:13:08 PM UTC-2, Thiago Adams wrote:


To produce a number from 

> 100..001
> --------
> 300..000

You also need to implement some algorithm like in the paper.
0,33..3336666...

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

#138652

On 10/12/2018 19:12, Thiago Adams wrote:
> On Monday, December 10, 2018 at 4:24:30 PM UTC-2, Bart wrote:

>> How does it work with pencil and paper calculations (for something you
>> don't already know)?
> 
> 
> Using "paper"
> 

> 100..001
> --------
> 300..000
> 
> To do math like in the paper, we need symbolic math.

If you simplify a little, the paper calculation starts off like this:
      ________________
   3 |1 0 0 1

I get a sequence that looks this:

   _ 3 3 3 6 6 6 ...

The question, the same question that was asked of my library, is at what 
point do you stop? How do you know when you have enough digits, or have 
the answer?

Sometimes there will be no remainder after an iteration, and that answer 
will be exact. But sometimes there will always be a remainder.

> You need to have more types. You need
> a type for fractions (you can use bigint
> for numerator and denominator).

The decision has already been made not to use rational types.

> For instance sin(x) is the same of
> 
>      x^3    x^5
> x-  --- + ----  .. (Maclaurin Expansion of sin(x))
>       3!     5!
> 
> then using bigint we can compute sin(10) for instance
> with many digits using this serie.
> 
> sin(PI) will be necessary other method.
> 
> So this is really interesting in my opinion
> much more than big real.
You can still do all this stuff. But when you do need to evaluate the 
answer, then you will need big float routines.

You can do a certain amount with only big integers, but automatically 
dealing with scaled numbers isn't that much harder to implement and 
makes it all much easier to work with.

You don't really want to represent pi as 31459265358979... / 
1000000000000000... if working in decimal, or whatever ratio it would be 
in binary. Perhaps 106902858... / 2**128.

And that wouldn't be enough, as an expression like 'π' would evaluate to 
a whole number: 3.

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

#138670

On Monday, December 10, 2018 at 7:44:35 PM UTC-2, Bart wrote:
> On 10/12/2018 19:12, Thiago Adams wrote:
> > On Monday, December 10, 2018 at 4:24:30 PM UTC-2, Bart wrote:
> 
> >> How does it work with pencil and paper calculations (for something you
> >> don't already know)?
> > 
> > 
> > Using "paper"
> > 
> 
> > 100..001
> > --------
> > 300..000
> > 
> > To do math like in the paper, we need symbolic math.
> 
> If you simplify a little, the paper calculation starts off like this:
>       ________________
>    3 |1 0 0 1
> 
> I get a sequence that looks this:
> 
>    _ 3 3 3 6 6 6 ...
> 
> The question, the same question that was asked of my library, is at what 
> point do you stop? How do you know when you have enough digits, or have 
> the answer?
> 
> Sometimes there will be no remainder after an iteration, and that answer 
> will be exact. But sometimes there will always be a remainder.


I wrote a function using your library to print in decimal form
any rational number. ( I will add this function in my lib as well)


#include <stdio.h>
#include "bigint.h"

void PrintDecimals(Bigint numerator, Bigint denominator, int ndigits)
{
  Bigint quotient = bn_div(numerator , denominator);  
  bn_print(quotient);

  Bigint remainder = bn_sub(numerator , bn_mul(quotient , denominator));

  //has remainder?
  if (!bn_iszero(remainder))
  {
    printf(".");
    
    int digits = 0;
    while (!bn_iszero(remainder))
    {
      remainder = bn_mul(remainder , bn_make("10"));
      quotient = bn_div(remainder , denominator);            
      bn_print(quotient);
      remainder = bn_sub(remainder, bn_mul(quotient, denominator));
      digits++;
      if (digits > ndigits) {
        break;
      }
    }
  }  
}

int main(void) {

  Bigint a = bn_make("100001");
  Bigint b = bn_make("300000");

  PrintDecimals(a, b, 30);

  bn_free(a);
  bn_free(b);
}


A extra interesting function is to detect the repetition.

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

#138679

On 12/11/2018 10:20 AM, Thiago Adams wrote:
> On Monday, December 10, 2018 at 7:44:35 PM UTC-2, Bart wrote:
>> On 10/12/2018 19:12, Thiago Adams wrote:
>>> On Monday, December 10, 2018 at 4:24:30 PM UTC-2, Bart wrote:
>>
>>>> How does it work with pencil and paper calculations (for something you
>>>> don't already know)?
>>>
>>>
>>> Using "paper"
>>>
>>
>>> 100..001
>>> --------
>>> 300..000
>>>
>>> To do math like in the paper, we need symbolic math.
>>
>> If you simplify a little, the paper calculation starts off like this:
>>        ________________
>>     3 |1 0 0 1
>>
>> I get a sequence that looks this:
>>
>>     _ 3 3 3 6 6 6 ...
>>
>> The question, the same question that was asked of my library, is at what
>> point do you stop? How do you know when you have enough digits, or have
>> the answer?
>>
>> Sometimes there will be no remainder after an iteration, and that answer
>> will be exact. But sometimes there will always be a remainder.
> 
> 
> I wrote a function using your library to print in decimal form
> any rational number. ( I will add this function in my lib as well)
> 
> 
> #include <stdio.h>
> #include "bigint.h"
> 
> void PrintDecimals(Bigint numerator, Bigint denominator, int ndigits)
> {
>    Bigint quotient = bn_div(numerator , denominator);
>    bn_print(quotient);
> 
>    Bigint remainder = bn_sub(numerator , bn_mul(quotient , denominator));
> 
>    //has remainder?
>    if (!bn_iszero(remainder))
>    {
>      printf(".");
>      
>      int digits = 0;
>      while (!bn_iszero(remainder))
>      {
>        remainder = bn_mul(remainder , bn_make("10"));
>        quotient = bn_div(remainder , denominator);
>        bn_print(quotient);
>        remainder = bn_sub(remainder, bn_mul(quotient, denominator));
>        digits++;
>        if (digits > ndigits) {
>          break;
>        }
>      }
>    }
> }
> 
> int main(void) {
> 
>    Bigint a = bn_make("100001");
>    Bigint b = bn_make("300000");
> 
>    PrintDecimals(a, b, 30);
> 
>    bn_free(a);
>    bn_free(b);
> }
> 
> 
> A extra interesting function is to detect the repetition.

One of the cycle detection algorithms should work. Not sure how good 
they would scale here.

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

#138621

David Brown <david.brown@hesbynett.no> writes:
[...]
> IMHO, the only thing you should consider about errno is that it was a 
> terrible idea.  Using a global variable as a return vale /really/ limits 
> things.  Suddenly you have all sorts of complications about side-effects 
> of your otherwise "pure" or "const" functions, trouble when 
> multi-threading, no chance of constexpr functions (if Bart ever wants to 
> take that route), etc.
[...]

The threading issue was addressed by making errno thread-local.

N1570 7.5 says that errno is a macro "which expands to a modifiable
lvalue that has type int and thread local storage duration".  In the
implementation I'm using, it expands to `(*__errno_location ())`.  This
was changed in C11.

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

#138627

On 08/12/2018 21:14, Keith Thompson wrote:
> David Brown <david.brown@hesbynett.no> writes:
> [...]
>> IMHO, the only thing you should consider about errno is that it was a
>> terrible idea.  Using a global variable as a return vale /really/ limits
>> things.  Suddenly you have all sorts of complications about side-effects
>> of your otherwise "pure" or "const" functions, trouble when
>> multi-threading, no chance of constexpr functions (if Bart ever wants to
>> take that route), etc.
> [...]
> 
> The threading issue was addressed by making errno thread-local.

Yes.  And if Bart were to introduce a similar concept to errno in his 
library, he'd need to do that too.  And while it is certainly doable, it 
is equally certainly a complication.

> 
> N1570 7.5 says that errno is a macro "which expands to a modifiable
> lvalue that has type int and thread local storage duration".  In the
> implementation I'm using, it expands to `(*__errno_location ())`.  This
> was changed in C11.
> 

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

#138622

On 12/8/2018 6:13 AM, David Brown wrote:
> On 07/12/2018 22:43, Anton Shepelev wrote:
>> Bart:
>>
>>> 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
>>
>> Great job of making it lean and clean!
>>
>> You decision to abort on errors imposes is a severe
>> limitaiton on the usability of the library, whereas status
>> returns would make it clumsier.  Have you considered
>> errno.h?
>>
> 
> IMHO, the only thing you should consider about errno is that it was a 
> terrible idea.  Using a global variable as a return vale /really/ limits 
> things. 

Fwiw, errno should be thread local in a multi-threaded environment:

http://www.unix.org/whitepapers/reentrant.html

Actually, they moved away from errno, notice how it is not used here:

http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mutex_lock.html

Well, the damn semaphores still use per-thread errno:

http://pubs.opengroup.org/onlinepubs/7908799/xsh/sem_wait.html

I have seen a lot of broken sem_waits that fail to loop on EINTR. This 
can create a nest of deadly race conditions just waiting to cast their 
nasty data-corrupting influence across everything, like a damn virus.

;^o


> Suddenly you have all sorts of complications about side-effects 
> of your otherwise "pure" or "const" functions, trouble when 
> multi-threading, no chance of constexpr functions (if Bart ever wants to 
> take that route), etc.
> 
> Bart's latest thoughts of using an interface style "bm_add(x, a, b);" 
> rather than "x = bm_add(a, b);" is a good one, and it opens for the idea 
> of a status return if that suits his needs.
> 

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

#138698

On 04/12/2018 12:17, 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
> 
> This library, although providing the most basic functions and using the 
> simplest algorithms, nevertheless ticks quite a few of my boxes:

That library has been superseded by this one which also does floating point:

     https://github.com/sal55/mx/blob/master/bignum.md

Links to .h and .c files are at the top, followed by some docs.

Only just finished porting it to C, and it will be tested more over next 
few days. The floating point part is experimental, and lacks the 
mathematical functions that normally go with that.

The API here is a little more sophisticated with less fiddly memory 
management.

About double the size of the bigint library, but it's still one module 
and it still avoids most bothersome C features such as macros and 
conditional code, so still ticks my boxes.

It should run on anything with at least a 32-bit int and 64-bit long 
long int, and should compile with anything especially C99+.

-- 
bart

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

#139063

On Tue, 04 Dec 2018 12:17:58 +0000, 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)
> 
> * Does not use 'struct T' types, only 'T'
> 
> * Does not use macros at all
> 
> * Does not use conditional code
> 
> * Makes strict use of 'extern' and 'static' for functions
> 
> * Always uses {...} braces around statements
> 
> * Will work with almost any C compiler. (Needs stdint.h and a 64-bit
>    type. Linux systems may not like the "%lld"; in that case, since I
>    can't fix C's type system, just define int64 in terms of long long
>    int.)
> 
> * Does not need makefiles or configuration steps
> 
> * Simple test (using the demo main() in bigint.h) tested on a dozen
>    compilers on 3 OSes.
> 
> * Can be statically linked in to any program; just add the bigint.c
>    module.
> 
> * To build as a shared library, use for example:
> 
>       gcc -shared bigint.c -obigint.dll
> 
> 
> (This is version 0.0 derived from a version in my language
> (https://github.com/sal55/mx/blob/master/bigint.m), which was itself
> derived as a standalone library from the big integer routines in my
> interpreter.)

Thanks actually for posting this, I am excited to read the source code 
some time soon. Good and concise and great comments!



-- 
That's me, Deavmi.

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

#139069

On 25/12/2018 12:59, Tristan B. Kildaire wrote:
> On Tue, 04 Dec 2018 12:17:58 +0000, 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

> Thanks actually for posting this, I am excited to read the source code
> some time soon. Good and concise and great comments!


There two libraries now; that one above, and a new one 'bignum.c':

   https://github.com/sal55/mx/blob/master/bignum.h
   https://github.com/sal55/mx/blob/master/bignum.c

This one is bigger, but also does floating point, is a bit faster, and 
is easier to use when calling the functions directly (rather than 
wrapped via an extra layer). The interface is more gmp-like.

Examples:

   https://github.com/sal55/mx/blob/master/pidemo.c    # uses bignum
   https://github.com/sal55/mx/blob/master/pidemo2.c   # uses bigint

[toc] | [prev] | [standalone]

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

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

csiph-web