copying algorithms: GNU Scientific Library vs Numerical Recipes

13 Nov 2004

      Witam,
  What can be legally (and morally) copied from a program
under a restrictive copyright is "the algorithms, the ideas" but not
the particular way of expressing them.

So the practical question is: where is the borderline?

In the GSL (GNU Scientific Library), http://www.gnu.org/software/gsl/,
GNU provides, e.g. in Version 1.1.1, the version below of NR's
ran0 routine.

i'm sure most of us have access to a legal copy of the NR routine,
or else a little googling shows e.g.

http://cc.oulu.fi/~tf/tiedostot/pub/nrf/ran0.f

Well, to me these look extremely similar to one another. Even the
constants:

static const long int m = 2147483647, a = 16807, q = 127773, r = 2836;
static const unsigned long int mask = 123459876;

are exactly identical to those in the NR routines, they even have the
same names, except for the "i".  Is this really a different "expression"?

In any case, IMHO noone can deny that the authors of the GSL routines
(there is also ran1, ran2, ran3) have very likely had access to the NR
source code.

Sure, they translated it to C and added some stuff, but it's the
same algorithm, it's essentially the same sequence of steps.

Anyway, GSL has lots of really cool stuff. :)   Let's defend scientific
software freedom!

pozdr
boud

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

/* rng/ran0.c
 *
 * Copyright (C) 1996, 1997, 1998, 1999, 2000 James Theiler, Brian Gough
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <config.h>
#include <stdlib.h>
#include <gsl/gsl_errno.h>
#include <gsl/gsl_rng.h>

/* This is an implementation of the algorithm used in Numerical
   Recipe's ran0 generator. It is the same as MINSTD with an XOR mask
   of 123459876 on the seed.

   The period of this generator is 2^31.

   Note, if you choose a seed of 123459876 it would give a degenerate
   series 0,0,0,0, ...  I've made that into an error. */

static inline unsigned long int ran0_get (void *vstate);
static double ran0_get_double (void *vstate);
static void ran0_set (void *state, unsigned long int s);

static const long int m = 2147483647, a = 16807, q = 127773, r = 2836;
static const unsigned long int mask = 123459876;

typedef struct
  {
    unsigned long int x;
  }
ran0_state_t;

static inline unsigned long int
ran0_get (void *vstate)
{
  ran0_state_t *state = (ran0_state_t *) vstate;

  const unsigned long int x = state->x;

  const long int h = x / q;
  const long int t = a * (x - h * q) - h * r;

  if (t < 0)
    {
      state->x = t + m;
    }
  else
    {
      state->x = t;
    }

  return state->x;
}

static double
ran0_get_double (void *vstate)
{
  return ran0_get (vstate) / 2147483647.0 ;
}

static void
ran0_set (void *vstate, unsigned long int s)
{
  ran0_state_t *state = (ran0_state_t *) vstate;

  if (s == mask)
    {
      GSL_ERROR_VOID ("ran0 should not use seed == mask",
				GSL_EINVAL);
    }

  state->x = s ^ mask;

  return;
}

static const gsl_rng_type ran0_type =
{"ran0",			/* name */
 2147483646,			/* RAND_MAX */
 1,				/* RAND_MIN */
 sizeof (ran0_state_t),
 &ran0_set,
 &ran0_get,
 &ran0_get_double};

const gsl_rng_type *gsl_rng_ran0 = &ran0_type;

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

Boud Roukema

Michal Frackowiak

Boud Roukema

Michal Frackowiak

Boud Roukema

tags

participants (2)