Same algorithm in c++ and python but different output

Question

C++

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
unsigned long long int t,n,i,m,su,s,k;
int main()
{
        cin>>n;
        if(n==0)
        {
            cout<<"0\n";
            return 0;
        }
        m = sqrt(n);
        su = m*(m+1)/2;
        s = n-1;
        for(i=2;i*i<=n;i++)
        {
            k = n/i;
            s = s + (k-1)*i + k*(k+1)/2 - su;
        }
        cout<<s<<"\n";
}

Python

import math
n = int(input())
if n==0:
    print('0')
else:
    m = int(math.sqrt(n))
    su = int(m*(m+1)/2)
    s = n-1
    i=2
    while i*i<=n:
        k = int(n/i)
        s = s + ((k-1)*i) + int(k*(k+1)/2) - su
        i = i+1
    print(s)

answer coming different for 1000000000
for c++ code output = 322467033612360628
for python code output = 322467033612360629
why are the answers different? I don't think it is caused by overflow in c++ integer because in a 64 bit environment range of unsigned long long int is 18,446,744,073,709,551,615

Edit :removed the variable t it was creating confusion

What version of python are you using? When I run your python code with python 2.7 I get 322467033612360628 which matches your c++ output. — Mark B
– Mark B, Commented Sep 20, 2013 at 16:11
This expression: s = 125000001750008744 + ((333333333-1)*3) + int(333333333*(333333333+1)/2) - 499991253 yields different results in python2 and python3. — Robᵩ
– Robᵩ, Commented Sep 20, 2013 at 16:17
Edit :removed the variable t it was creating confusion - A good reason to always provide the simplest program that recreates the problem. See SSCCE.ORG. — Robᵩ
– Robᵩ, Commented Sep 20, 2013 at 16:21

dawg · Accepted Answer · 2013-09-20 17:36:47Z

This is related to the change in the division operator in Python 3 vs Python 2.

In Python 2, the / is integer floor division if both numerator and denominator are integers:

Python 2.7.1 (r271:86882M, Nov 30 2010, 10:35:34) 
[GCC 4.2.1 (Apple Inc. build 5664)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 2/3
0
>>> 2.0/3.0
0.6666666666666666
>>> 
>>> 1/2 == 1.0 / 2.0
False

Notice that in Python 2, if either numerator or denominator are floats, the result will be a float.

But Python 3 changes the / to be 'True Division' and you need to use // to get integer floor division:

Python 3.3.2 (default, May 21 2013, 11:50:47) 
[GCC 4.2.1 Compatible Apple Clang 4.1 ((tags/Apple/clang-421.11.66))] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 2/3
0.6666666666666666
>>> 2//3
0
>>> 1/2 == 1.0/2.0
True
>>> 1//2 == 1.0/2.0
False

C++ uses floor division between integers:

int main()
{
    int n=2;
    int d=3;
    cout<<n/d;    // 0
}

If I run this code (adapted from yours):

from __future__ import print_function

import math
n = 1000000000
if n==0:
    print('0')
else:
    m = int(math.sqrt(n))
    su = int(m*(m+1)/2)
    s = n-1
    i=2
    while i*i<=n:
        k = int(n/i)
        s = s + ((k-1)*i) + int(k*(k+1)/2) - su
        i = i+1
    print(s)

Under Python 3 I get:

322467033612360629

Under Python 2 I get:

322467033612360628

If you change this line:

s = s + ((k-1)*i) + int(k*(k+1)/2) - su

to

s = s + ((k-1)*i) + int(k*(k+1)//2) - su # Note the '//'

it will fix the problem under Python 3

Collectives™ on Stack Overflow

Same algorithm in c++ and python but different output

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related