How to make Python run as fast (or faster) than Julia

[bartc]

On 26/02/2018 11:40, Chris Angelico wrote:
> On Mon, Feb 26, 2018 at 10:13 PM, bartc <bc at freeuk.com> wrote:
>> Below is the first draft of a Python port of a program to do with random
>> numbers. (Ported from my language, which in turned ported it from a C
>> program by George Marsaglia, the random number guy.)
>>
>> However, running it quickly exhausts the memory in my machine. The reason is
>> that Python unhelpfully widens all results to bignums as needed. The code
>> relies on calculations being modulo 2^64.
>>
>> Note that restricting integer ops to 64 bits probably still won't work, as I
>> believe the numbers need to be unsigned.
> 
> No, it's because the original implementation assumed integer
> wrap-around (at least, I think that's what's happening; I haven't
> analyzed the code in great detail). That means all your integer
> operations are doing two jobs: the one they claim to, and then a
> masking to 64 bits signed. That's two abstract operations that happen,
> due to the nature of the CPU, to work efficiently together. If you
> don't implement both halves of that in your Python port, you have
> failed at porting. What if you were porting a program from a 72-bit
> chip that assumed Binary Coded Decimal? Would you complain that C's
> integers are badly behaved?
> 
> And that's without even asking whether a C program that assumes
> integer wrap-around counts as portable. At least with Python, you have
> a guarantee that integer operations are going to behave the same way
> on all compliant implementations of the language.


A C version is given below. (One I may have messed around with, which 
I'm not sure works properly. For an original, google for Marsaglia and 
KISS64 or SUPRKISS64.)

Most integers are unsigned, which have well-defined overflow in C (they 
just wrap as expected). In C, a mixed signed/unsigned op is performed as 
unsigned.

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

/*   SUPRKISS64.c, period 5*2^1320480*(2^64-1)   */
#include <stdio.h>
#include <stdlib.h>
#include "timer.c"
  static signed long long Q[20632],
                  carry=36243678541LL,
                  xcng=12367890123456LL,
                  xs=521288629546311LL,
                  indx=20632;

  #define CNG ( xcng=6906969069LL*xcng+123 )
  #define XS  ( xs^=xs<<13,xs^=xs>>17,xs^=xs<<43 )
  #define SUPR ( indx<20632 ? Q[indx++] : refill() )
  #define KISS SUPR+CNG+XS

  signed long long refill(void) {
   int i; signed long long z,h;
   for(i=0;i<20632;i++) {
     h = (carry&1);
     z = ((Q[i]<<41)>>1)+((Q[i]<<39)>>1)+(carry>>1);
     carry = (Q[i]>>23)+(Q[i]>>25)+(z>>63);
     Q[i] = ~((z<<1)+h);
   }
   indx=1;
   return (Q[0]);
  }

  int main() {
   int i; signed long long x;

   for(i=0;i<20632;i++) Q[i]=CNG+XS;

   for(i=0;i<1000000000;i++) x=KISS;

   printf("Does x=4013566000157423768\n     x=%llu.\n",x);
}

-- 
bartc