Trying to replicate small C code in Python

Question

I'm trying to replicate some C code in python.

Here is the C code.

#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
 double p = 1.0 - q;
 double lambda = z * (q / p);
 double sum = 1.0;
 int i, k;
 for (k = 0; k <= z; k++)
 {
  double poisson = exp(-lambda);
  for (i = 1; i <= k; i++)
    poisson *= lambda / i;
    sum -= poisson * (1 - pow(q / p, z - k));
 }
 return sum;
}

The C code is just modelling this equation, taken from Bitcoin's whitepaper

Here is my attempt in python.

def BitcoinAttackerSuccessProbablity(q, z):
    # probablity of honest finding the next node is 1 - probablity the attacker will find the next
    p = 1 - q
    # lambda is equal to the number of blocks times by the division of attacker and honest finding the next block
    lam = z * (q / p)
    sum = 1.0
    i = 1
    k = 0

    while k <= z:
        poisson = math.exp(-1 * lam)
        while i <= k:
            poisson = poisson * (lam / i)
            i = i + 1
        sum = sum - (poisson * (1 - ((q / p) ** (z - k))))
        k = k + 1

    print(sum)


for x in range(0,11):
    BitcoinAttackerSuccessProbablity(0.1, x)

The results from the C code are. (q and z are inputs while P is an output.)

q=0.1    

z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012

I am trying to replicate these results accurately in python by converting the C code. My first 3 results (z=0,-3) are correct, however, the remaining results are incorrect. When I changed my while loop to the equivalent in C only the first two results where correct.

The results from my Python code

1.0
0.20458727394278242
0.05097789283933862
-0.057596282822218514
-0.1508215598462347
-0.22737700216279746
-0.28610012088884856
-0.3272432217416562
-0.3519591169464781
-0.36186779773540745
-0.35878211836275675

I think it's something simple on how loops are handled between languages.

Any help would be much appreciated

edit:

Here is the first attempt

def BitcoinAttackerSuccessProbablity(q, z):
# probablity of honest finding the next node is 1 - probablity the attacker will find the next
p = 1 - q
#lambda is equal to the number of blocks times by the division of attacker and honest finding the next block
lam = z * (q/p)
sum = 1.0


for k in range(0, z):
    poisson = math.exp(-1*lam)
    for i in range(1, k):
        poisson = poisson * (lam/i)
    sum = sum - (poisson * (1 - ((q/p)**(z-k))))

print(sum)

Hi @Hack_Hut! I've indented your code in the way I think it was intended. In the future, please take the time to present your code nicely; it makes it easier to read and to run. — AJF
– AJF, Commented Apr 11, 2018 at 21:40
I moved your i = 1 into the outer loop and got results that look essentially the same as the C output. — Fred Larson
– Fred Larson, Commented Apr 11, 2018 at 21:42

score 3 · Accepted Answer · 2018-04-11 21:47:38Z

3

You aren't reinitializing i to zero before the while i <= k loop.

A more idiomatic (and much shorter!) way of writing this in Python would be to use a generator expression with the sum() function to perform the summation, as well as using the math.factorial() function instead of calculating the factorial in a loop. Using this approach, the code becomes a pretty direct translation of the original mathematical formula:

def BitcoinAttackerSuccessProbablity(q, z):
    # probablity of honest finding the next node is 1 - probablity the attacker
    # will find the next
    p = 1 - q
    # lambda is equal to the number of blocks times by the division of attacker
    # and honest finding the next block
    lam = z * (q / p)

    return 1 - sum(
            (lam ** k) * math.exp(-lam) / math.factorial(k)
            * (1 - (q / p) ** (z - k))
            for k in range(0, z+1)
            )

Note that the range is set as range(0, z+1) instead of range(0, z), because Python ranges do not include the stop value.

edited Apr 11, 2018 at 21:47

answered Apr 11, 2018 at 21:43

user149341

Sign up to request clarification or add additional context in comments.

2 Comments

Hack_Hut Over a year ago

Absolute live saver, been scratching my head for over 2 hours on this simple bug. Cheers :)

Jenny from Xory Over a year ago

Satoshi Nakamoto?

Collectives™ on Stack Overflow

Trying to replicate small C code in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related