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

Groups > comp.lang.python > #88572 > unrolled thread

Best search algorithm to find condition within a range

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

Contents

  Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 02:44 -0700
    Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 09:29 -0400
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:10 -0700
        Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 10:26 -0400
        Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:34 +1000
      Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-07 14:29 +0000
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:36 -0700
          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:49 +1000
            Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-07 15:05 +0000
              Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:23 -0400
              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 01:37 +1000
              Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 17:02 +0100
          Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 16:00 +0100
            Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:43 -0700
              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:51 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:46 +1000
          Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:04 -0400
          Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 09:06 -0600
            Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:47 -0700
              Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:06 -0400
              Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:49 +1200
          Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:36 +1000
            Re: Best search algorithm to find condition within a range Cameron Simpson <cs@zip.com.au> - 2015-04-08 08:51 +1000
          Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:01 -0400
          Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-18 18:08 +0000
            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-19 23:02 +1000
              Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-19 17:56 +0300
                Re: Best search algorithm to find condition within a range Gene Heskett <gheskett@wdtv.com> - 2015-04-19 11:17 -0400
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-20 12:53 +1000
              Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-19 14:52 -0400
              Re: Best search algorithm to find condition within a range Paul Rubin <no.email@nospam.invalid> - 2015-04-19 13:44 -0700
              Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-25 14:49 +0000
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 09:18 -0700
    Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 08:32 -0600
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:40 -0700
        Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 12:33 -0400
          Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 10:07 -0700
            Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 11:44 -0600
              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:38 +1000
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 11:18 +1000
                  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:37 -0600
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:19 -0700
                  Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 13:39 +0000
                    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 07:56 -0700
                      Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 17:33 +0000
                        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:28 -0700
                          Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:36 -0700
                            Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:28 +0100
                          Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:29 +0100
            Re: Best search algorithm to find condition within a range Terry Reedy <tjreedy@udel.edu> - 2015-04-07 14:55 -0400
            Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:19 -0600
              Re: Best search algorithm to find condition within a range Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 20:27 +0100
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 15:35 -0700
                  Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 20:38 -0400
                  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:35 -0600
                    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:28 -0700
                      Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:35 -0600
                    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:35 -0700
            Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 05:25 +1000
            Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:28 -0600
            Re: Best search algorithm to find condition within a range Serhiy Storchaka <storchaka@gmail.com> - 2015-04-07 23:57 +0300
            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:18 +1000
              Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-08 07:31 +0300
        Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 14:15 -0600
        Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-07 21:42 +0100
      Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:55 +1000
        Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:30 -0600
    Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:57 +1000
      Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:59 +1200
        Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 02:39 +0100
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:12 -0700
      Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:49 +1000
        Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-09 12:32 +1000
          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-09 12:39 +1000
            Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 23:14 -0700
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 22:50 -0700
      Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:07 -0700
        Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:18 -0700
          Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-08 17:27 +0000
            Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 10:50 -0700
      Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-08 22:22 +0100
        Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 01:06 +0300
          Re: Best search algorithm to find condition within a range Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-08 17:01 -0700
          Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-09 10:19 +0100
            Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 13:00 +0300
              Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 13:57 +0200
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 15:45 +0300
                  Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 14:56 +0200
                    Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-09 09:19 -0400
                      Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:33 +0300
                        Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:49 +0300
                        Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 15:57 +0200
                          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 00:08 +1000
                            Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 16:53 +0200
                              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:02 +1000
                                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:12 -0700
                                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:21 +1000
                                  Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:36 +1000
                                  Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-09 17:40 +0100
                            Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 07:54 -0700
                              Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 09:03 -0600
                                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:21 -0700
                                  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 10:23 -0600
                        Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:11 +1000
                          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:34 +1000
                            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 02:15 +1000
                              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:36 +1000
                                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:49 +1000
                            Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 19:25 +0300
                              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:43 +1000
                                Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 16:53 +0000
                                  Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:00 +1000
                                    Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 17:44 +0000
                                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:41 +1000
                                  Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 04:07 +1000
                                    Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:14 +0300
                                  Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:11 +0300
                                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 20:43 +0300
                              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:35 +1000
                                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:56 +1000
                                  Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 23:18 +1000
                                    Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 23:41 +1000
                                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:15 +0300
                                Re: Best search algorithm to find condition within a range Rustom Mody <rustompmody@gmail.com> - 2015-04-10 09:39 -0700
                    Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:28 +0300

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

#88686

On 07/04/2015 23:57, Steven D'Aprano wrote:
> On Tue, 7 Apr 2015 07:44 pm, jonas.thornvall@gmail.com wrote:
>
>
>> I want todo faster baseconversion for very big bases like base 1 000 000,
>> so instead of adding up digits i search it.
>
> What digits would you use for base one-million?
>
> Base 2 uses 0 1.
> Base 3 uses 0 1 2.
> Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
>
> Base one million uses what?
>
> How would you write down 12345 in base one-million?
>

That's only necessary when printing out the numbers as text (or reading 
them in). Even then, you don't need a million unique symbols; groups of 
letters or digits will do. The simplest way to represent a digit is 
write it out in normal base 10.

So the the number 3,012,345, in base 1000000, could represented in text 
form as the two 'digit':

  (3, 12345)

ie. 3*1000000 + 12345*1. In internal binary, each digit can just be 
stored in the normal form, probably as one digit per 32-bit integer.

(I have a big integer library that works exactly this way, using a 
decimal representation, but using base 1000000 with digits 0 to 999999, 
rather than base 10 and digits 0 to 9.)

-- 
Bartc

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

#88689

BartC <bc@freeuk.com>:

> So the the number 3,012,345, in base 1000000, could represented in
> text form as the two 'digit':
>
>  (3, 12345)
>
> ie. 3*1000000 + 12345*1. In internal binary, each digit can just be
> stored in the normal form, probably as one digit per 32-bit integer.
>
> (I have a big integer library that works exactly this way, using a
> decimal representation, but using base 1000000 with digits 0 to
> 999999, rather than base 10 and digits 0 to 9.)

It is common to implement big integers in base-2**16, base-2**32 or
base-2**64. Arithmetics is performed just like in elementary school.


Marko

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

#88691

On Wed, Apr 8, 2015 at 3:06 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> BartC <bc@freeuk.com>:
>
>> So the the number 3,012,345, in base 1000000, could represented in
>> text form as the two 'digit':
>>
>>  (3, 12345)
>>
>> ie. 3*1000000 + 12345*1. In internal binary, each digit can just be
>> stored in the normal form, probably as one digit per 32-bit integer.
>>
>> (I have a big integer library that works exactly this way, using a
>> decimal representation, but using base 1000000 with digits 0 to
>> 999999, rather than base 10 and digits 0 to 9.)
>
> It is common to implement big integers in base-2**16, base-2**32 or
> base-2**64. Arithmetics is performed just like in elementary school.

While basically true, its not quite true: there are generally more
efficient but more complex algorithms for the computations than are
typically taught in school. For example, multiplication will often be
done with the Karatsuba algorithm, which is O(n^1.585)[1], rather than
long multiplication, which is O(n^2). Processors internally often use
shift-and-add, which is a variation on long multiplication, and is
fairly easy to implement in hardware for fixed-size integers.

[1] http://en.wikipedia.org/wiki/Karatsuba_algorithm

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

#88700

On 08/04/2015 23:06, Marko Rauhamaa wrote:
> BartC <bc@freeuk.com>:
>
>> So the the number 3,012,345, in base 1000000, could represented in
>> text form as the two 'digit':
>>
>>   (3, 12345)
>>
>> ie. 3*1000000 + 12345*1. In internal binary, each digit can just be
>> stored in the normal form, probably as one digit per 32-bit integer.
>>
>> (I have a big integer library that works exactly this way, using a
>> decimal representation, but using base 1000000 with digits 0 to
>> 999999, rather than base 10 and digits 0 to 9.)
>
> It is common to implement big integers in base-2**16, base-2**32 or
> base-2**64.

This was a development of a version that used base-10 strings to encode 
the numbers.

It might be a magnitude slower than, say, built-in Python big integers, 
but a huge advantage had been in being able to print out the results 
easily without needing division.

(I know that there is some algorithm to print an arbitrary precision 
binary number using shifts and masks, but I didn't know it then.)

 > Arithmetics is performed just like in elementary school.

Not in the school I went to; we used decimal!

-- 
Bartc

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

#88703

BartC <bc@freeuk.com>:

> On 08/04/2015 23:06, Marko Rauhamaa wrote:
>> Arithmetics is performed just like in elementary school.
>
> Not in the school I went to; we used decimal!

The basic arithmetic algorithms are independent of the base.

For example, here's how you can add two 128-bit integers in C using
64-bit digits:

    typedef struct {
        uint64_t lo, hi;
    } uint128_t;

    uint128_t add128(uint128_t x, uint128_t y)
    {
        uint128_t result = {
            .lo = x.lo + y.lo,
            .hi = x.hi + y.hi
        };
        if (result.lo < x.lo)
            result.hi++;
        return result;
    }

Works both for signed and unsigned integers.    


Marko

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

#88710

Marko Rauhamaa <marko@pacujo.net> writes:

> The basic arithmetic algorithms are independent of the base.

Right.

> For example, here's how you can add two 128-bit integers in C using
> 64-bit digits:
>
>     typedef struct {
>         uint64_t lo, hi;
>     } uint128_t;
>
>     uint128_t add128(uint128_t x, uint128_t y)
>     {
>         uint128_t result = {
>             .lo = x.lo + y.lo,
>             .hi = x.hi + y.hi
>         };
>         if (result.lo < x.lo)
>             result.hi++;
>         return result;
>     }
>
> Works both for signed and unsigned integers.    

(Slightly off-topic, but...)

No, it would not work for signed integers (i.e., with lo and hi of
int64_t type), because overflow is undefined behavior for signed.

-- Alain.

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

#88712

Alain Ketterlin <alain@dpt-info.u-strasbg.fr>:

> No, it would not work for signed integers (i.e., with lo and hi of
> int64_t type), because overflow is undefined behavior for signed.

All architectures I've ever had dealings with have used 2's-complement
integers. Overflow is well-defined, well-behaved and sign-independent
wrt addition, subtraction and multiplication (but not division).


Marko

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

#88713

Marko Rauhamaa <marko@pacujo.net> writes:

> Alain Ketterlin <alain@dpt-info.u-strasbg.fr>:
>
>> No, it would not work for signed integers (i.e., with lo and hi of
>> int64_t type), because overflow is undefined behavior for signed.
>
> All architectures I've ever had dealings with have used 2's-complement
> integers. Overflow is well-defined, well-behaved and sign-independent
> wrt addition, subtraction and multiplication (but not division).

You are confused: 2's complement does not necessarily mean modular
arithmetic. See, e.g.,
http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c

-- Alain.

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

#88714

On 04/09/2015 08:56 AM, Alain Ketterlin wrote:
> Marko Rauhamaa <marko@pacujo.net> writes:
>
>> Alain Ketterlin <alain@dpt-info.u-strasbg.fr>:
>>
>>> No, it would not work for signed integers (i.e., with lo and hi of
>>> int64_t type), because overflow is undefined behavior for signed.
>>
>> All architectures I've ever had dealings with have used 2's-complement
>> integers. Overflow is well-defined, well-behaved and sign-independent
>> wrt addition, subtraction and multiplication (but not division).
>
> You are confused: 2's complement does not necessarily mean modular
> arithmetic. See, e.g.,
> http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c
>

So the C standard can specify such things as undefined.  The 
architecture still will do something specific, right or wrong, and 
that's what Marko's claim was about.  The C compiler has separate types 
for unsigned and for signed, while the underlying architecture of every 
twos complement machine I have used did add, subtract, and multiply as 
though the numbers were unsigned (what you call modular arithmetic).

In my microcoding days, the ALU did only unsigned arithmetic, while the 
various status bits had to be interpreted to decide whether a particular 
result was overflow or had a carry.  It was in interpreting those status 
bits that you had to use the knowledge of whether a particular value was 
signed or unsigned.

Then the microcode had to present those values up to the machine 
language level.  And at that level, we had no carry bits, or overflow, 
or anything directly related.

-- 
DaveA

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

#88716

Dave Angel <davea@davea.name>:

> So the C standard can specify such things as undefined. The
> architecture still will do something specific, right or wrong, and
> that's what Marko's claim was about. The C compiler has separate types
> for unsigned and for signed, while the underlying architecture of
> every twos complement machine I have used did add, subtract, and
> multiply as though the numbers were unsigned (what you call modular
> arithmetic).

Alain did have a point. *If* I had used int64_t in my algorithm, it
might not have worked because the compiler could legally produce code
that crashes or does weird things in case of a signed integer overflow.

In this day and age, heavily optimized compilers (including gcc)
actively exploit undefined behavior in code generation.

However, I didn't use int64_t, I used uint64_t.


Marko

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

#88717

Marko Rauhamaa <marko@pacujo.net>:

> In this day and age, heavily optimized compilers (including gcc)
> actively exploit undefined behavior in code generation.

Example: Find the value of INT_MAX programmatically.

========================================================================
#include <stdio.h>

int main()
{
    int n = 1;
    while (n + 1 > n)
        n++;
    printf("%d\n", n);
    return 0;
}
========================================================================

========================================================================
$ # Use gcc-4.9.2
$ cc -o test test.c
$ ./test
2147483647
$ cc -O9 -o test test.c
$ ./test
^C
========================================================================

The command "cc -S -O9 test.c" shows that the compiler compiles the
while loop into:

========================================================================
.L2:
        jmp     .L2
========================================================================


Marko

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

#88718

Marko Rauhamaa <marko@pacujo.net> writes:

> Dave Angel <davea@davea.name>:
>
>> So the C standard can specify such things as undefined. The
>> architecture still will do something specific, right or wrong, and
>> that's what Marko's claim was about. The C compiler has separate types
>> for unsigned and for signed, while the underlying architecture of
>> every twos complement machine I have used did add, subtract, and
>> multiply as though the numbers were unsigned (what you call modular
>> arithmetic).
>
> Alain did have a point. *If* I had used int64_t in my algorithm, it
> might not have worked because the compiler could legally produce code
> that crashes or does weird things in case of a signed integer
> overflow.

Yes, exactly. Since the language semantics don't guarantee anything, the
compiler can do whatever it likes. Changing your example to use int64_t
instead of uint64_t would let the compiler remove the "overflow" test.
Because, in:

    z = x+y; // all signed ints
    if ( z < x )
        ...

either there was no overflow (and the condition is false), or there was,
and the result is undefined, i.e., "z<x" can be considered false also.

> In this day and age, heavily optimized compilers (including gcc)
> actively exploit undefined behavior in code generation.

They do. Moreover, it looks like it is very difficult to warn the user
(I'm not even sure compilers catch cases like the one above).

> However, I didn't use int64_t, I used uint64_t.

Yes, your code was ok.

-- Alain.

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

#88719

On Thu, Apr 9, 2015 at 11:57 PM, Alain Ketterlin
<alain@dpt-info.u-strasbg.fr> wrote:
> Because, in:
>
>     z = x+y; // all signed ints
>     if ( z < x )
>         ...
>
> either there was no overflow (and the condition is false), or there was,
> and the result is undefined, i.e., "z<x" can be considered false also.

Do you mean "all unsigned ints" here? Because if y is negative, the
condition will be true without overflow. If you didn't, then I'm
puzzled as to where the undefined behaviour is coming from.

ChrisA

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

#88721

Chris Angelico <rosuav@gmail.com> writes:

> On Thu, Apr 9, 2015 at 11:57 PM, Alain Ketterlin
> <alain@dpt-info.u-strasbg.fr> wrote:
>> Because, in:
>>
>>     z = x+y; // all signed ints
>>     if ( z < x )
>>         ...
>>
>> either there was no overflow (and the condition is false), or there was,
>> and the result is undefined, i.e., "z<x" can be considered false also.
>
> Do you mean "all unsigned ints" here? Because if y is negative, the
> condition will be true without overflow. If you didn't, then I'm
> puzzled as to where the undefined behaviour is coming from.

Ouch, you're right, I tried to stick with Marko's example and forgot the
basics. I meant "signed ints", but the "removable" condition should be
something like:

    if ( x>0 && y>0 && z<x )
        ...

i.e., some condition that is never true (either false or undefined).
Thanks for the correction.

If the variables are all unsigned ints, the potential overflow has a
well-defined meaning, and the code is correct and doesn't trigger
undefined behavior. This was Marko's initial example.

-- Alain.

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

#88723

On Fri, Apr 10, 2015 at 12:53 AM, Alain Ketterlin
<alain@dpt-info.u-strasbg.fr> wrote:
> Ouch, you're right, I tried to stick with Marko's example and forgot the
> basics. I meant "signed ints", but the "removable" condition should be
> something like:
>
>     if ( x>0 && y>0 && z<x )
>         ...
>
> i.e., some condition that is never true (either false or undefined).
> Thanks for the correction.

Ah, yep. And yes, that's absolutely right - the compiler's allowed to
treat that as never true.

ChrisA

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

#88727

Den torsdag 9 april 2015 kl. 17:02:24 UTC+2 skrev Chris Angelico:
> On Fri, Apr 10, 2015 at 12:53 AM, Alain Ketterlin
> <alain@dpt-info.u-strasbg.fr> wrote:
> > Ouch, you're right, I tried to stick with Marko's example and forgot the
> > basics. I meant "signed ints", but the "removable" condition should be
> > something like:
> >
> >     if ( x>0 && y>0 && z<x )
> >         ...
> >
> > i.e., some condition that is never true (either false or undefined).
> > Thanks for the correction.
> 
> Ah, yep. And yes, that's absolutely right - the compiler's allowed to
> treat that as never true.
> 
> ChrisA

I guess when working on highlevel arithmetic one does not need to think about such trivial? things, the expression is broken down into pairs fed into the functions and the parser handle the signs?

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

#88729

On Fri, 10 Apr 2015 01:02 am, Chris Angelico wrote:

> On Fri, Apr 10, 2015 at 12:53 AM, Alain Ketterlin
> <alain@dpt-info.u-strasbg.fr> wrote:
>> Ouch, you're right, I tried to stick with Marko's example and forgot the
>> basics. I meant "signed ints", but the "removable" condition should be
>> something like:
>>
>>     if ( x>0 && y>0 && z<x )
>>         ...
>>
>> i.e., some condition that is never true (either false or undefined).
>> Thanks for the correction.
> 
> Ah, yep. And yes, that's absolutely right - the compiler's allowed to
> treat that as never true.

Am I missing something? Did you over-trim the quoting?

How can the compiler possibly be allowed to treat x>0 && y>0 && z<x as
always false?

x = y = 1
z = 0

gives x>0 && y>0 && z<x as true.



-- 
Steven

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

#88731

On Fri, Apr 10, 2015 at 1:21 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 10 Apr 2015 01:02 am, Chris Angelico wrote:
>
>> On Fri, Apr 10, 2015 at 12:53 AM, Alain Ketterlin
>> <alain@dpt-info.u-strasbg.fr> wrote:
>>> Ouch, you're right, I tried to stick with Marko's example and forgot the
>>> basics. I meant "signed ints", but the "removable" condition should be
>>> something like:
>>>
>>>     if ( x>0 && y>0 && z<x )
>>>         ...
>>>
>>> i.e., some condition that is never true (either false or undefined).
>>> Thanks for the correction.
>>
>> Ah, yep. And yes, that's absolutely right - the compiler's allowed to
>> treat that as never true.
>
> Am I missing something? Did you over-trim the quoting?

Yes, because the significant line was about three levels of quote
back, so I didn't bother to go retrieve it. Immediately before the if:

z = x + y;

ChrisA

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

#88739

On 2015-04-09 16:21, Steven D'Aprano wrote:
> On Fri, 10 Apr 2015 01:02 am, Chris Angelico wrote:
>
>> On Fri, Apr 10, 2015 at 12:53 AM, Alain Ketterlin
>> <alain@dpt-info.u-strasbg.fr> wrote:
>>> Ouch, you're right, I tried to stick with Marko's example and forgot the
>>> basics. I meant "signed ints", but the "removable" condition should be
>>> something like:
>>>
>>>     if ( x>0 && y>0 && z<x )
>>>         ...
>>>
>>> i.e., some condition that is never true (either false or undefined).
>>> Thanks for the correction.
>>
>> Ah, yep. And yes, that's absolutely right - the compiler's allowed to
>> treat that as never true.
>
> Am I missing something? Did you over-trim the quoting?
>
> How can the compiler possibly be allowed to treat x>0 && y>0 && z<x as
> always false?
>
> x = y = 1
> z = 0
>
> gives x>0 && y>0 && z<x as true.
>
Earlier in the thread there was the line:

     z = x+y; // all signed ints

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

#88722

Den torsdag 9 april 2015 kl. 16:08:48 UTC+2 skrev Chris Angelico:
> On Thu, Apr 9, 2015 at 11:57 PM, Alain Ketterlin
> <alain@dpt-info.u-strasbg.fr> wrote:
> > Because, in:
> >
> >     z = x+y; // all signed ints
> >     if ( z < x )
> >         ...
> >
> > either there was no overflow (and the condition is false), or there was,
> > and the result is undefined, i.e., "z<x" can be considered false also.
> 
> Do you mean "all unsigned ints" here? Because if y is negative, the
> condition will be true without overflow. If you didn't, then I'm
> puzzled as to where the undefined behaviour is coming from.
> 
> ChrisA

Aside from the base changer i've written a bignumb anybase generic multiplication, addition and subtraction routine. My goal is to make the arithmetic in the base of choice whatever size.

And i think i can do it, i already have mult, add , subt working in anybase but not bignumb.

Does this mult work for arbitrary size?
Or will it but out at some point?


<SCRIPT LANGUAGE="Javascript">
/* MULTIPLY TWO VARIABLES */

//CONVERT A DECIMAL NUMBER INTO ANYBASE
function newbase(decNumber,base){
var out =[];
digits=1;
digmult=1;
while(digmult*base<=decNumber){
	digmult=digmult*base
        digits++;
}
digsave=digmult;
while(decNumber>0 || digits>0){
        loop=1;
        digit=0;
       	for (digit=0;digit<=base;digit++) {
        if((digit+1)*digmult>decNumber)break;
       	}
        out[digits]=digit;
        digmult=digmult*digit;
        decNumber=decNumber-digmult;
        digsave=digsave/base;
        digmult=digsave;
        digits--;
	}

return out;

}

function naiveMult(base, multOne, multTwo)
{  
   var total = [];
   var addResult = [];
   total[0] = 0;

   //Check which array bigger minimize multiplications
   if (multOne.length>multTwo.length){ mshort=multOne.length; mlong=multTwo.length;}
       else { mshort=multOne.length; mlong=multTwo.length;}

   for (var i = 0; i < mshort; i ++ )
   {
      multresult = [];
      remainder = 0;
      tempVal = 0;
      tempDig = 0;
      j = 0;

      if(i > 0)
      {
         for(zero = 0; zero < i; zero ++ ) multresult[zero] = 0;
      }

      while(j < mlong)
      {
         intMult++;
           
         tempVal = (multOne[i] * multTwo[j]) + remainder;
         remainder = 0;

         if (tempVal >= base)
         {
            tempDig = tempVal % base;
            remainder = (tempVal - tempDig) / base;
            multresult[j + i] = tempDig;
         }
         else
         {
            multresult[j + i] = tempVal;
         }
         j ++ ;
      }

      if(remainder != 0)
      {
         multresult[j + i] = remainder;
      }
      addResult=naiveAdd(base, total, multresult);
      total=addResult; 
   }
   return total;
}

/* ADD TWO VARIABLES */

function naiveAdd(base, arrOne, arrTwo)
{
   
   shortArr=[];
   longArr=[];
   addResult = [];
   remainder = 0;
   //Find shortest and longest array
   if (arrOne.length >= arrTwo.length) {shortArr = arrTwo; longArr = arrOne;}
            else  {shortArr = arrOne;longArr = arrTwo;}
   for (i = 0; i < shortArr.length; i ++ )
   {
      intAdd ++ ;
      arrOne[i] = parseInt(arrOne[i]);
      arrTwo[i] = parseInt(arrTwo[i]);
      if (isNaN(arrOne[i])) arrOne[i] = 0;
      if (isNaN(arrTwo[i])) arrTwo[i] = 0;
      addResult[i] = arrOne[i] + arrTwo[i] + remainder;
     
      if (addResult[i] >= base)
      {
         addResult[i] = addResult[i] - base;
         remainder = 1;
      }
      else
      {
         remainder = 0;
      }
   }
   //Copying values from the shorter string
   while(i<longArr.length) {longArr[i]=parseInt(longArr[i]);addResult[i]=longArr[i]+remainder; remainder=0; i++;}
   //If strings of equal lenght but there is a remainder;
   if (remainder == 1) addResult[i++] = 1;
   else addResult.splice(i, 1);
   return addResult;
}

/* MAIN */
function fetchValues()
{
intMult=0;
intAdd=0;
base=10;
x=1;
y=1;
document.calc.result.value="";
document.calc.stats.value="";
document.calc.outbase.value="";
strEval = document.calc.eval.value;
genArr = strEval.split("*");
//fONE=newbase(genArr[0],base);
//document.write(fONE[2]);
//document.calc.outbase.value +=fONE+" + \n";
//fTWO=newbase(genArr[1],base);
//document.calc.outbase.value +=fTWO+"\n";

arrOne=genArr[0].split("").reverse();
arrTwo=genArr[1].split("").reverse();
base = document.calc.formbase.value;
out=naiveMult(base,arrOne,arrTwo);
document.calc.stats.value +="Multiplications = "+intMult+"\n";
document.calc.result.value +=" Product = " + out.reverse()+"\n";
}
</SCRIPT>
<!DOCTYPE html>
<html lang="en">
<head><meta charset="utf-8"/></head>
<body bgcolor="gold" onload="fetchValues()">
<H1>Big numbers</H1><P>
<FORM name=calc onSubmit="fetchValues(); return false;">
<B>INPUT DEC-><input type=submit name="calc" value="Calc"> <input type="text" name="eval" value="32432439*12" size="300"><br>
BASE <input type="text" name="formbase" value="10" size="10"><br>
This calculation<input type="text" name="outbase" value="" size="60"><br>
<FONT COLOR="white">
RESULT<br>
<textarea name="result" rows="20" cols="120"></textarea><br>
STATUS</B><br>
<textarea name="stats" cols="120" rows="40" value=""></textarea>
</FORM>
</body>
</html>

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

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

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

csiph-web