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

#88724

On Thu, Apr 9, 2015 at 8:54 AM,  <jonas.thornvall@gmail.com> wrote:
> 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?

Dunno, I have no interest in verifying your code for you. Especially
since this is a Python list and said code is not Python.

If you want to build confidence that your code works, I suggest
writing some unit tests for it. (I'd also suggest keeping it separate
from your html in a .js file, which would make it a lot easier to test
and reuse.)

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

#88728

Den torsdag 9 april 2015 kl. 17:04:53 UTC+2 skrev Ian:
> On Thu, Apr 9, 2015 at 8:54 AM,  <jonas.thornvall@gmail.com> wrote:
> > 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?
> 
> Dunno, I have no interest in verifying your code for you. Especially
> since this is a Python list and said code is not Python.
> 
> If you want to build confidence that your code works, I suggest
> writing some unit tests for it. (I'd also suggest keeping it separate
> from your html in a .js file, which would make it a lot easier to test
> and reuse.)

Well with the condition i can get the bignumb arithmetic fully working, i am on my way of working bignumb arithmetic in anybase. 

I think this will be the first implementation ever to use arithmetic in the base of your choice. 

And i know for a fact (i've factored RSA in the 200 digit range on a 486 in a couple of hours 98-) 

So there is more to this than fancy overlay, it is about the digit representation at the binary level, and how the binary groups interpretated.

So in the end, even with none optimised type like Javascript integer it will save operations at high level as well as lowlevel.

That said highlevel and highbase arithmetic will work alot faster than binary.
And using modular arithmetic you may find out that some operations requiering exponential work like factoring will turn out to be done in polynomial time.

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

#88737

On Thu, Apr 9, 2015 at 9:21 AM,  <jonas.thornvall@gmail.com> wrote:
> And i know for a fact

What do you know for a fact?

> (i've factored RSA in the 200 digit range on a 486 in a couple of hours 98-)

Bullshit. RSA-200 wasn't factored until 2005, and the group that did
it required three months on a cluster of 80 2.2-GHz Opterons.

http://en.wikipedia.org/wiki/RSA_numbers#RSA-200

If you're going to spout lies in order to try to create credentials
for yourself that we don't care about anyway, at least try to keep it
in the realm of believability.

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

#88726

On Thu, 9 Apr 2015 11:33 pm, Marko Rauhamaa wrote:

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

Optimization and undefined behaviour reminds me of a story my wife told me,
of a time she was crossing the US with some roadies. As they were driving
across the desert highway, one of the roadies noticed that they were
driving in the wrong direction for their next gig.

"Who cares?" said the driver, "we're making fantastic time!"


-- 
Steven

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

#88730

On Fri, Apr 10, 2015 at 1:11 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Thu, 9 Apr 2015 11:33 pm, Marko Rauhamaa wrote:
>
>> In this day and age, heavily optimized compilers (including gcc)
>> actively exploit undefined behavior in code generation.
>
> Optimization and undefined behaviour reminds me of a story my wife told me,
> of a time she was crossing the US with some roadies. As they were driving
> across the desert highway, one of the roadies noticed that they were
> driving in the wrong direction for their next gig.
>
> "Who cares?" said the driver, "we're making fantastic time!"

It's not really like that. Imagine you're loading up the stuff on the
back of your truck. Do you have to research the narrowest tunnel
you'll ever have to go through? Nah. You just make sure it's no wider
than the legal limit, because any tunnel that's narrower than that
isn't your problem. If you ever _do_ meet an overly-narrow tunnel,
you'll run into problems, because you assumed that such a thing wasn't
possible.

The C compiler is generally going to assume a whole slew of principles
that aren't technically guaranteed. For instance, it'll probably
assume that CPU registers will accurately retain what they were set
to, and likewise memory (unless it's marked 'volatile'). Put your code
out in space, and that might no longer be true, but you can't expect
the compiler to cope with that. As far as it's concerned, it's
impossible for a CPU register to arbitrarily change without notice.
It's equally impossible for the addition of two positive signed
integers to result in a negative integer.

ChrisA

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

#88734

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

> It's equally impossible for the addition of two positive signed
> integers to result in a negative integer.

Why oh why do C programmers tell such porkies??? *semi-wink*

[steve@ando c]$ gcc add.c
[steve@ando c]$ ./a.out
a = 1
b = 2147483647
a+b = -2147483648


Looks like a negative integer to me, but then, given that its undefined
behaviour, perhaps the compiler flipped some pixels on the screen so it
merely *looks* negative.


Here's the source code:

[steve@ando c]$ cat add.c
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int a;
  a = 1;
  int b;
  b = 2147483647;
  printf("a = %d\n", a);
  printf("b = %d\n", b);
  printf("a+b = %d\n", a+b);
  return 0;
}



-- 
Steven

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

#88738

On Fri, Apr 10, 2015 at 2:15 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 10 Apr 2015 01:34 am, Chris Angelico wrote:
>
>> It's equally impossible for the addition of two positive signed
>> integers to result in a negative integer.
>
> Why oh why do C programmers tell such porkies??? *semi-wink*
>
> [steve@ando c]$ gcc add.c
> [steve@ando c]$ ./a.out
> a = 1
> b = 2147483647
> a+b = -2147483648
>
>
> Looks like a negative integer to me, but then, given that its undefined
> behaviour, perhaps the compiler flipped some pixels on the screen so it
> merely *looks* negative.

Precisely. Another compiler, or another CPU architecture, is welcome
to behave differently. *According to the C standard*, you just did
something impossible, so it's equally valid for the output to be 5, 3,
7, or 25, all of which would probably be produced by Princess Ida's
compiler. (Mind you, her compiler might do that when asked to add 2
and 2, so I'm not sure it's all that helpful a comparison. [1])

> Here's the source code:
>
> [steve@ando c]$ cat add.c
>   a = 1;
>   b = 2147483647;
>   printf("a+b = %d\n", a+b);

The first undefined part here is that this operation might not even
overflow. If the compiler uses a 64-bit int, this will simply produce
2147483648. But even assuming that it can't represent that total in a
signed int, there's nothing in the spec that says it has to become
negative.

ChrisA

[1] http://diamond.boisestate.edu/gas/princess_ida/webop/pi_10d.html

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

#88747

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

> *According to the C standard*, you just did something impossible

Woo-hoo! I can do the impossible! Immovable objects? I juggle them like
rubber balls. Unstoppable forces? I don't even notice them. The very gods
themselves will fear me!



-- 
Steven

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

#88735

Chris Angelico <rosuav@gmail.com>:

> As far as it's concerned, it's impossible for a CPU register to
> arbitrarily change without notice. It's equally impossible for the
> addition of two positive signed integers to result in a negative
> integer.

The standard says that any program that takes a signed integer out of
its valid range is broken and deserves anything that happens to it.

I say it's the standard that is broken.


Marko

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

#88740

On Fri, Apr 10, 2015 at 2:25 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Chris Angelico <rosuav@gmail.com>:
>
>> As far as it's concerned, it's impossible for a CPU register to
>> arbitrarily change without notice. It's equally impossible for the
>> addition of two positive signed integers to result in a negative
>> integer.
>
> The standard says that any program that takes a signed integer out of
> its valid range is broken and deserves anything that happens to it.
>
> I say it's the standard that is broken.

For application work, it's usually much better to have an integer type
like Python's or Pike's int - a signed integer that can never
overflow. For low-level bit manipulation work, you usually want an
*unsigned* integer of specific size, with well defined wrap-around
behaviour. When do you actually want a signed integer with
well-defined overflow behaviour?

ChrisA

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

#88741

On 2015-04-09, Chris Angelico <rosuav@gmail.com> wrote:

> For application work, it's usually much better to have an integer
> type like Python's or Pike's int - a signed integer that can never
> overflow. For low-level bit manipulation work, you usually want an
> *unsigned* integer of specific size, with well defined wrap-around
> behaviour. When do you actually want a signed integer with
> well-defined overflow behaviour?

http://en.wikipedia.org/wiki/Binary_scaling#Binary_angles

-- 
Grant Edwards               grant.b.edwards        Yow! HELLO KITTY gang
                                  at               terrorizes town, family
                              gmail.com            STICKERED to death!

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

#88742

On Fri, Apr 10, 2015 at 2:53 AM, Grant Edwards <invalid@invalid.invalid> wrote:
> On 2015-04-09, Chris Angelico <rosuav@gmail.com> wrote:
>
>> For application work, it's usually much better to have an integer
>> type like Python's or Pike's int - a signed integer that can never
>> overflow. For low-level bit manipulation work, you usually want an
>> *unsigned* integer of specific size, with well defined wrap-around
>> behaviour. When do you actually want a signed integer with
>> well-defined overflow behaviour?
>
> http://en.wikipedia.org/wiki/Binary_scaling#Binary_angles

Huh, interesting. (Trust the list to have an answer to a rhetorical
question, though to be honest, I should have expected that there'd be
some.) A cursory glance at that Wikipedia page suggests that unsigned
wrap-around can be used just as effectively, though, so I'm not sure
this is at all an argument for standardizing the behaviour of signed
wrap-around.

ChrisA

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

#88746

On 2015-04-09, Chris Angelico <rosuav@gmail.com> wrote:
> On Fri, Apr 10, 2015 at 2:53 AM, Grant Edwards <invalid@invalid.invalid> wrote:
>> On 2015-04-09, Chris Angelico <rosuav@gmail.com> wrote:
>>
>>> For application work, it's usually much better to have an integer
>>> type like Python's or Pike's int - a signed integer that can never
>>> overflow. For low-level bit manipulation work, you usually want an
>>> *unsigned* integer of specific size, with well defined wrap-around
>>> behaviour. When do you actually want a signed integer with
>>> well-defined overflow behaviour?
>>
>> http://en.wikipedia.org/wiki/Binary_scaling#Binary_angles
>
> Huh, interesting. (Trust the list to have an answer to a rhetorical
> question, though to be honest, I should have expected that there'd be
> some.) A cursory glance at that Wikipedia page suggests that unsigned
> wrap-around can be used just as effectively, though, so I'm not sure
> this is at all an argument for standardizing the behaviour of signed
> wrap-around.

Applications that use BAMs depend on the fact that you can treat them
as either signed or unsigned values and get correct results.

Relative headings are often treated as signed values with 0 meaning
"straight ahead" with deltas to the right/starboard as positive and
deltas to the left/port as negative. If I were to add three (or seven,
or eleven) -90 degree deltas to my heading of 0, I'd expect end up
with a relative heading of +90.  That depends on signed overflow
working correctly.

Absolute headings (e.g. relative to North), are often treated as
unsigned values.  If I start with a heading of 300, add 90 degrees, I
would expect to get an answer of 30.

That means you can freely mix signed and unsigned BAM values, and then
treat the result as either signed or unsigned, and you still get the
right answer.

With most 2's compliment ALU hardware, you get the desired signed
overflow/underflow "for free" because at the gate level it's exactly
the same as the unsigned behavior.

And back in the day, if you let the Navy pick the CPU, there was even
a single machine instruction that would convert a register pair from a
cartesian (X,Y) tuple to a polar (t,r) tuple (or vice versa).  And the
t value was in BAMs.  The various trig transcendental instructions
worked with angles in BAMs.

Python was not availble for that platform, so this is a bit of a
digression. :)

-- 
Grant Edwards               grant.b.edwards        Yow! Do you think the
                                  at               "Monkees" should get gas on
                              gmail.com            odd or even days?

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

#88744

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

> For application work, it's usually much better to have an integer type
> like Python's or Pike's int - a signed integer that can never
> overflow. For low-level bit manipulation work, you usually want an
> unsigned integer of specific size, with well defined wrap-around
> behaviour. When do you actually want a signed integer with
> well-defined overflow behaviour?

I'm lead to believe that such a thing is useful in crypto, although I don't
quite see it myself.

There are good ways to deal with out-of-range results in systems languages:

- well-defined wrap-around behaviour;
- saturation;
- trapping.

"Do whatever the hell the compiler feels like doing" is not one of them.

More discussion here:

http://blog.regehr.org/archives/642


-- 
Steven

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

#88750

On Fri, Apr 10, 2015 at 3:41 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> There are good ways to deal with out-of-range results in systems languages:
>
> - well-defined wrap-around behaviour;
> - saturation;
> - trapping.
>
> "Do whatever the hell the compiler feels like doing" is not one of them.

Systems languages are already going to be somewhat close to the metal.
They're an alternative to rewriting your code completely for every
platform you're on. If you have to guard a few small sections with
configure-time checks, that's still saved you the work of writing all
the rest of your code twice.

With applications languages, as earlier mentioned, none of this should
be necessary. Sacrifice the performance and have arbitrary-precision
integers, Unicode strings, garbage collection, and first-class
lists/functions/mappings etc. This is only about lower-level
languages.

ChrisA

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

#88752

Chris Angelico <rosuav@gmail.com>:

> With applications languages, as earlier mentioned, none of this should
> be necessary. Sacrifice the performance and have arbitrary-precision
> integers, Unicode strings, garbage collection, and first-class
> lists/functions/mappings etc. This is only about lower-level
> languages.

While Unicode is great, modulo arithmetics is much closer to my heart
than Unicode -- as an application programmer. Only today I released a
product feature that actively exploits the wrapping semantics.


Marko

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

#88751

Steven D'Aprano <steve+comp.lang.python@pearwood.info>:

> There are good ways to deal with out-of-range results in systems
> languages:
>
> - well-defined wrap-around behaviour;
> - saturation;
> - trapping.

Some months back I reported a bug in LXDE's CPU monitor applet: after a
couple of months of operation, the CPU monitor displayed a 100% CPU
utilization rate on an idle machine (on a 32-bit machine).

The reason was that scanf("%ld") saturated at LONG_MAX instead of
wrapping gracefully. Wrapping behavior would have resulted in a
perfectly well-behaved difference (and CPU utilization). As it stood,
saturation destroyed the sane-looking calculation.

The solution was to move to scanf("%lld") and prevent satufation. Again,
I don't blame the code; I blame the spec. Writing a wrapping
implementation of scanf("%ld") is the simplest possible, most obvious
and most obviously correct approach. Only it wouldn't be
standards-compliant.


Marko

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

#88745

Chris Angelico <rosuav@gmail.com>:

> For low-level bit manipulation work, you usually want an *unsigned*
> integer of specific size, with well defined wrap-around behaviour.
> When do you actually want a signed integer with well-defined overflow
> behaviour?

Bit manipulation is not the issue here.

The reason for signed, wrapping integers is that you want to be able to
perform signed subtractions. Consider for example time differences that
are often expressed as signed second and/or nanosecond counts that are
at the brink of overflowing. You want to be able to perform usual
arithmetic operations even if the intermediate results overflow.

A classic analogy: the roots of a cubic equation can be figured out
explicitly with Cardano's method <URL:
http://www.math.vanderbilt.edu/~schectex/courses/cubic/>. The
algebraists were impressed with the solution, but to their
consternation, the formula involved taking the square root of a negative
number even when all three solutions were real.

Temporary integer overflows and excursions into the complex number space
should not be shunned unnecessarily.


Marko

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

#88743

On Fri, 10 Apr 2015 02:25 am, Marko Rauhamaa wrote:

> Chris Angelico <rosuav@gmail.com>:
> 
>> As far as it's concerned, it's impossible for a CPU register to
>> arbitrarily change without notice. It's equally impossible for the
>> addition of two positive signed integers to result in a negative
>> integer.
> 
> The standard says that any program that takes a signed integer out of
> its valid range is broken and deserves anything that happens to it.
> 
> I say it's the standard that is broken.

It's not so much the undefined behaviour part that gets me. That's bad
enough. But the concept that having the compiler ignore what you write in
the source code because you've accidentally hit some undefined part of the
spec *is a feature* rather than a horrible, horrible design flaw that blows
my mind.

http://blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx

A *sane* language developer would insist that if the compiler is smart
enough to detect a bug, say a pointer which might be null but is
dereferenced regardless, it should *stop compiling and tell you*, not treat
it as an excuse to do something radically different from what the source
code says. Calculating the wrong result really quickly is not an
optimization except in the minds of crazy people, its a bug.

Code intended to sanitize untrusted code was turned into a no-op.
http://code.google.com/p/nativeclient/issues/detail?id=245

A check that a pointer wasn't null was removed by the compiler, creating an
exploitable vulnerability. https://isc.sans.edu/diary.html?storyid=6820

I've come to the conclusion that C is the PHP of low level languages. Like
PHP, it's popularity is at least in part due to its lack of consistency and
psychotic design. That, I think, is the secret of success for some
languages: you appeal to the cowboy coders by giving them something tricky
to use, but not too tricky, something which doesn't require the discipline
and intellectual rigour (and/or cleverness) of writing code which is
actually correct, so long as they can write code which is *almost* correct
and have it mostly work. What do a few buffer overflows, seg faults, and
incorrect results matter when the resulting code runs like a rocket?

C: calculating more wrong answers in less time than any other language!

Of course not all C programmers are cowboys. Linux Torvalds has a reputation
for a zero-tolerance attitude towards kernel bugs, and a take-no-prisoners
attitude to anyone who might break userspace code due to changes in the
kernel. But I think that the vast number of C/C++ exploitable bugs is proof
that most C coders lack either the skill or inclination to write correct C
code. Even the Linux kernel contains bugs. Things were bad enough in the
old days of classical C compilers, but modern C optimizing compilers may
actively counteract your code as you have written it. How that isn't
considered an outright malicious act, I don't know.



-- 
Steven

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

#88748

On Fri, Apr 10, 2015 at 3:35 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> It's not so much the undefined behaviour part that gets me. That's bad
> enough. But the concept that having the compiler ignore what you write in
> the source code because you've accidentally hit some undefined part of the
> spec *is a feature* rather than a horrible, horrible design flaw that blows
> my mind.

In Python, you can create an assert with a side effect. This is
something you should never do, and the compiler is free to optimize
that side effect out. Is that outright malicious? The only difference
is that in Python, it's well-defined - you can *depend* on that code
being optimized out under certain specific conditions, rather than it
depending on the compiler. (At least, I think that's the case. Is it
legal for a Python implementation to fully evaluate asserts and then
simply not raise the exception?)

Take this example:

def spam(lst):
    assert lst[0] < lst[1]
    # carry on with the rest of the code

If lst is a Python list, this is side-effect free. But what if it
isn't? What if __getitem__ actually mutates the object? The assertion
can be dropped, and the getitem calls not made. Is that a horrible,
horrible design flaw in Python, or is it an ill-designed object that
does things that programmers should be allowed to assume never happen?

ChrisA

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

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

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

csiph-web