nCr Engine(C++) + A joke

[madurax86]

Full code is below its not optimized for speed if you can post the optimizations that can be implemented, heres a LOL that i came across when i was coding this last night.

Any Problems comments are welcome; there are a lot of C programmers in EK if you can translate this to C there are very few changes to be made ryt?

/*
factorial and nCr functions(not optimized)
==========================================
by madura.x86
comment: If you are getting minus values for a given nCr its because "long long"
type isnt enough try raising it to double, nothing wrong with the engine the 
values get awfully longer when n goes just after 51, have fun with it but dont 
just copy give credit where credit is due.
*/
#include <cstdlib>
#include <iostream>

using namespace std;
double fact(double i){
        double j,k;
        k=1;
        for (j=1;j<=i;j++) k=k*j;
        return k;
    }
long long nCr(int n, int r){
    int j,i,k,m1,n1;
    long long p,q;
    long long x[128],y[128];
    if (r>n) return 0;
    if (r==n) return 1;
    if (r==0) return 1;
    if (n<=2*r){
        k=0;
        for (j=n-r+1;j<=n;j++){
            k++;
            x[k]=j;
            }
        m1=k;
        k=0;
        for (i=2;i<=r;i++){
            k++;
            y[k]=i;
            }
        n1=k;
        }
        else
        {
            k=0;
            for (j=r+1;j<=n;j++){
                k++;
                x[k]=j;
            }
            m1=k;
            k=0;
            for (i=2;i<=n-r;i++){
                k++;
                y[k]=i;
            }
            n1=k;
            }
            
            for (j=1;j<=m1;j++)
                for (i=1;i<=n1;i++){
                    if (x[j]%y[i]==0){ 
                    x[j]=x[j]/y[i];
                    y[i]=1;}
                        
                    if (y[i]%x[j]==0){ 
                    y[i]=y[i]/x[j];
                    x[j]=1;}
                    }
            p=1;
            q=1;
            for (j=1;j<=m1;j++){
                if (x[j]!=1) p=p*x[j];}
            for (j=1;j<=n1;j++){
                if (y[j]!=1) q=q*y[j];
        }
    return p/q;
}

int main(int argc, char *argv[]){
    int i,j;
    j=51;
    for (i=0;i<j+1;i++){
            cout<<j<<"C"<<i<<" = "<<nCr(j,i)<<endl;
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

[madurax86]

results for n=51 highest that this thing can produce; for n>51 we have to use double but it outputs in scientific notation so its approx.

 

[madurax86]

katawath epaaaaaa do???

 

[HIVOLTAG3]

mm a scientific jork...

 

[madurax86]

mm a scientific jork...

ambe ekek wath reply kora!! hehe mona science da ban me simple math ne podak fast wena sulu karana system ekak damma normal factorial function walin nCr gananaya karana ba factorial function eka double return karana dammath nCr walata precision nati wenawa samahara welawata

results of normal nCr function using the fact() function n=51;

Sure it can go for more than 51 but precision isnt there because they tend to use scientific notation
Blogspot hates hot linking i just learned that !!

 

[HIVOLTAG3]

ambe ekek wath reply kora!! hehe mona science da ban me simple math ne podak fast wena sulu karana system ekak damma normal factorial function walin nCr gananaya karana ba factorial function eka double return karana dammath nCr walata precision nati wenawa samahara welawata

results of normal nCr function using the fact() function n=51;

Sure it can go for more than 51 but precision isnt there because they tend to use scientific notation
Blogspot hates hot linking i just learned that !!

ya itz nice to hv higher precision in everywhr. and thnx for the info mate..

but in practice,most of the time no 1 go after the 10^10+ numbers, so itz convinient to express them as a power of 10.

anyway nice to hv this kind of methodz ..

 

[madurax86]

ya itz nice to hv higher precision in everywhr. and thnx for the info mate..

but in practice,most of the time no 1 go after the 10^10+ numbers, so itz convinient to express them as a power of 10.

anyway nice to hv this kind of methodz ..

man nikan athal ekata ban haduwe ona ayata badu have ne ethota ...im gonna make a class for multiplying,dividing,adding,subtracting that will calculate the number as we do then we wont have to rely on normal double precision all numbers will be char arrays
check out the Calc in my blog a friend of mine coded a similar class in VB for that Calc 2048 digit precision me karana wada nathuwata karana ewa ban

 

[HIVOLTAG3]

man nikan athal ekata ban haduwe ona ayata badu have ne ethota ...im gonna make a class for multiplying,dividing,adding,subtracting that will calculate the number as we do then we wont have to rely on normal double precision all numbers will be char arrays
check out the Calc in my blog a friend of mine coded a similar class in VB for that Calc 2048 digit precision me karana wada nathuwata karana ewa ban

 

[Wolverine GTR]

He He.....
Nice Joke!!!!!!!!!

 

[chamidilk]

mokakda oke joke eka malayo.....
man nam ithin oya kagewath prog edit karanna nam yanne naha

 

[Im.Just.a.Fool]

parana thread awussala baladdi meka ahu une (mama thama awa witharaine). I wrote 3 methods to calculate nCr. ekin eka dannam. Java walin liwwe.

 

[Im.Just.a.Fool]

// The simplest way to calculate nCr, using factorial function. 
// This can calculate nCr upto n = 20.
 
    long fact(int n) {
        long x = 1;
        for (int i = 2; i <= n; i++) x *= i;
        return x;
    }
 
    long nCr(int n, int r) {
        return fact(n) / fact(r) / fact(n-r);
    }

 

[Im.Just.a.Fool]

// Another method to calculate nCr, this method can calculate 
// upto n = 29.

long nCr(int n, int r) {
    if (r > n / 2) r = n - r;
    long x = 1;
    for (int i = n; i > n-r; i--) x *= i;
    for (int i = 2; i <= r; i++) x /= i;
    return x;
}

 

[Im.Just.a.Fool]

// This method can calculate nCr upto n = 66. The largest value for nCr 
// that can be stored in a Java long variable is 7,219,428,434,016,265,740 
// (for n = 66, r = 33). The range of the type long in Java is from 
// -2^63 to 2^63-1. This method uses an array to store the prime factors 
// of the numbers that are multiplied and divided.
 
long nCr(int n, int r) {
    int[] pf = new int[n+1]; // n+1 is the length of the array pf.
    for (int i = n; i > n-r; i--) {
        int x = i;
        int j = 2;
        while (x >= j) {
            while (x % j == 0) {
                pf[j]++;
                x /= j;
            }
            j++;
        }
    }
    for (int i = 2; i <= r; i++) {
        int x = i;
        int j = 2;
        while (x >= j) {
            while (x % j == 0) {
                pf[j]--;
                x /= j;
            }
            j++;
        }
    }
    long res = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= pf[i]; j++) res *= i;
    }
    return res;
}

 

[Im.Just.a.Fool]

mamath meka wena karanna deyak nathi kamata liwwe . EK eke programming karana aya (both professionals and students) godak athine. ea ayath comments danawanam godak hondai .

 

[spgun]

Cordings r too long..

 

[Im.Just.a.Fool]

Cordings r too long..

If you can code a more efficient algorithm that can calculate nCr for larger values of n, please post it.

 

[Im.Just.a.Fool]

spgun,

Ok nevermind if it is efficient or not. oya kamathi onama widiyataka hadala post karanna. Then we can discuss about it.

 

[spgun]

I'll post it tomorrow.It's not with me right now.OK

 

[Im.Just.a.Fool]

I'll post it tomorrow.It's not with me right now.OK

OK.