www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Matrix creation quiz

reply bearophile <bearophileHUGS lycos.com> writes:
A little quiz. This is related to a recent post of mine in the main D
newsgroup, but please don't take a look at that post yet. This is the original
function:


double[][] matgen(int n) {
    double[][] a;
    double tmp = 1.0 / n / n;
    a.length = n;
    for (int i = 0; i < n; ++i) a[i].length = n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            a[i][j] = tmp * (i - j) * (i + j);
    return a;
}


Second "improved" version:

double[][] matgen(int n) {
    double tmp = 1.0 / n / n;
    auto a = new double[][](n, n);
    foreach (i, row; a)
        foreach (j, ref x; row)
            x = tmp * (i - j) * (i + j);
    return a;
}


But the second nicer version has a bug, do you see it? :-)

Bye,
bearophile
Apr 28 2011
next sibling parent reply Pedro Rodrigues <pdfrodrigues gmail.com> writes:
On 28-04-2011 13:02, bearophile wrote:

 A little quiz. This is related to a recent post of mine in the main D
newsgroup, but please don't take a look at that post yet. This is the original
function:


 double[][] matgen(int n) {
      double[][] a;
      double tmp = 1.0 / n / n;
      a.length = n;
      for (int i = 0; i<  n; ++i) a[i].length = n;
      for (int i = 0; i<  n; ++i)
          for (int j = 0; j<  n; ++j)
              a[i][j] = tmp * (i - j) * (i + j);
      return a;
 }


 Second "improved" version:

 double[][] matgen(int n) {
      double tmp = 1.0 / n / n;
      auto a = new double[][](n, n);
      foreach (i, row; a)
          foreach (j, ref x; row)
              x = tmp * (i - j) * (i + j);
      return a;
 }


 But the second nicer version has a bug, do you see it? :-)

 Bye,
 bearophile


The fact that 'i' and 'j' are deduced to type 'uint' in the second 
version. That's the kind of bug that would keep me up at night.

Cheers,
Pedro Rodrigues
Apr 28 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Pedro Rodrigues:


 The fact that 'i' and 'j' are deduced to type 'uint' in the second 
 version. That's the kind of bug that would keep me up at night.


Almost right answer. i and j are size_t, that is not uint in 64 bit
compilations. Unsigned numbers cause the (i-j) sub-expression to give wrong
results.

------------------------

Moritz Warning:


 I wonder, can there be done smth. on behalf of the language to prevent
 this kind of bug?


Two possible solutions, both refused by Walter:
- Dmd may use signed word for array indexes and lenghts.
- dmd may introduce runtime overflows.

Bye,
bearophile
Apr 28 2011
parent reply Don <nospam nospam.com> writes:
bearophile wrote:

 Pedro Rodrigues:
 

 The fact that 'i' and 'j' are deduced to type 'uint' in the second 
 version. That's the kind of bug that would keep me up at night.


 
 Almost right answer. i and j are size_t, that is not uint in 64 bit
compilations. Unsigned numbers cause the (i-j) sub-expression to give wrong
results.
 
 ------------------------
 
 Moritz Warning:
 

 I wonder, can there be done smth. on behalf of the language to prevent
 this kind of bug?


 
 Two possible solutions, both refused by Walter:
 - Dmd may use signed word for array indexes and lenghts.


Yes -- but see below.


 - dmd may introduce runtime overflows.


That would not fix this problem. You're doing arithmetic on unsigned 
values, where overflow doesn't happen.


Solution 3:
Dmd could use a special size_t type internally, defined as an integer of 
range equal to the address space. Internally, the compiler would view it 
as a long of range 0..cast(long)uint.max.
Thus, although it would implicitly convert to uint, it would not have 
uint semantics (size_t*size_t would no longer convert to uint).
But it wouldn't be an int, either. ( int a; if (a>b.length).. would be a 
signed/unsigned mismatch).

Incidentally a size_t type would allow us to catch bugs like:

uint n = a.length;
-- which compiles happily on 32 bits, but won't compile on a 64 bit 
system. I think it should be rejected on all systems.
Apr 29 2011
parent bearophile <bearophileHUGS lycos.com> writes:
I was away.

Don:


 That would not fix this problem. You're doing arithmetic on unsigned 
 values, where overflow doesn't happen.


My enhancement request about integral overflows asks for two compiler switches:
one that turns signed integral overflows (at compile time or run time) into
errors, and one switch that turns both signed and unsigned overflows into
errors. If you use the second switch you have overflows on unsigned values too.



 -- which compiles happily on 32 bits, but won't compile on a 64 bit 
 system. I think it should be rejected on all systems.


I agree. I think code that doesn't work on 64 bit systems has to not work on 32
bit ones too.

Bye,
bearophile
May 02 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 28 Apr 2011 08:02:40 -0400, bearophile <bearophileHUGS lycos.com>  
wrote:


 A little quiz. This is related to a recent post of mine in the main D  
 newsgroup, but please don't take a look at that post yet. This is the  
 original function:


 double[][] matgen(int n) {
     double[][] a;
     double tmp = 1.0 / n / n;
     a.length = n;
     for (int i = 0; i < n; ++i) a[i].length = n;
     for (int i = 0; i < n; ++i)
         for (int j = 0; j < n; ++j)
             a[i][j] = tmp * (i - j) * (i + j);
     return a;
 }


 Second "improved" version:

 double[][] matgen(int n) {
     double tmp = 1.0 / n / n;
     auto a = new double[][](n, n);
     foreach (i, row; a)
         foreach (j, ref x; row)
             x = tmp * (i - j) * (i + j);
     return a;
 }


 But the second nicer version has a bug, do you see it? :-)


I read the other answer, I thought it was because the indexing is  
different, but that's only on initialization.  So I was wrong :)

-Steve
Apr 28 2011
prev sibling next sibling parent Kagamin <spam here.lot> writes:
bearophile Wrote:


     auto a = new double[][](n, n);


And this really allocs tag array?

ps lol, didn't see the unsigned bug.
Apr 28 2011
prev sibling next sibling parent reply Moritz Warning <moritzwarning web.de> writes:
On Thu, 28 Apr 2011 08:02:40 -0400, bearophile wrote:


 A little quiz. This is related to a recent post of mine in the main D
 newsgroup, but please don't take a look at that post yet. This is the
 original function:


uhm, very sneaky.
I wonder, can there be done smth. on behalf of the language to prevent 
this kind of bug?
Apr 28 2011
parent reply Pedro Rodrigues <pdfrodrigues gmail.com> writes:
On 28-04-2011 16:39, Moritz Warning wrote:

 On Thu, 28 Apr 2011 08:02:40 -0400, bearophile wrote:


 A little quiz. This is related to a recent post of mine in the main D
 newsgroup, but please don't take a look at that post yet. This is the
 original function:


 uhm, very sneaky.
 I wonder, can there be done smth. on behalf of the language to prevent
 this kind of bug?


There sure is: disallow implicit conversion of types. That's how 
languages like Haskell work. It can be annoying having the compiler 
complain because you're using and 'int' where it expected a 'double' for 
example, but on the other hand it avoids many hard to detected bugs 
(like this one).

Pedro Rodrigues
Apr 28 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Pedro Rodrigues:


 There sure is: disallow implicit conversion of types.


In this program what are the implicit type conversions that cause the bug?

Bye,
bearophile
Apr 28 2011
prev sibling parent Ary Manzana <ary esperanto.org.ar> writes:
On 4/28/11 8:02 PM, bearophile wrote:

 A little quiz. This is related to a recent post of mine in the main D
newsgroup, but please don't take a look at that post yet. This is the original
function:


What are unsigned values good for?
Apr 29 2011