Author Topic: Programming V3 MEGATHREAD [Because we need one] (Read 6604 times)

BluetoothBoy · February 21, 2014, 08:27:36 AM

I'm guessing that the main reason Java is so popular is because it's widely available and works on 99.9% of everything. Otherwise, I think C++ would be in the lead by a wide margin - it's so much faster and takes far less processing power for the same amount of optimization.

Ad Bot · Advertisement

Ipquarx · February 21, 2014, 12:40:15 PM

Quote from: Blockzillahead on February 18, 2014, 07:41:10 PM

heres my best shot at rsa encryption. public code yo
Code: [Select]
bool isprime(long long num) //Function to check if number is prime { if(num <= 1) return false; if(num == 2) return true; if(num % 2 == 0) return false; for(int i = 3; i <= sqrt(num * 1.0); i += 2) { if(num % i == 0) return false; } return true; }

* Ipquarx internally screams at trial division primality checking

Blockzillahead · February 21, 2014, 12:41:35 PM

why lol

Lugnut · February 21, 2014, 12:42:44 PM

Does that rsa implementation have fast exponential modulus calculations, or does it do exponent THEN modulus?

Quote from: Blockzillahead on February 21, 2014, 12:41:35 PM

why lol

fantastically slow

Blockzillahead · February 21, 2014, 12:50:01 PM

Quote from: Lugnut on February 21, 2014, 12:42:44 PM

Does that rsa implementation have fast exponential modulus calculations, or does it do exponent THEN modulus? fantastically slow

fast exponential modulus calculation

am i supposed to do just the exponent first then modulus?

also how do i make the prime check faster

Lugnut · February 21, 2014, 01:13:33 PM

Quote from: Blockzillahead on February 21, 2014, 12:50:01 PM

am i supposed to do just the exponent first then modulus?

christ almighty no
you're talking loving crazy talk if you want to do that stuff in order

Quote from: Blockzillahead on February 21, 2014, 12:50:01 PM

also how do i make the prime check faster

"primality testing"
it can't give you a 100% positive yes or no, but it can give you like 99.99% positive
and it takes like 1% of the time
i dunno how it works, ipquarx does it ask him

Blockzillahead · February 21, 2014, 01:25:48 PM

Quote from: Lugnut on February 21, 2014, 01:13:33 PM

it can't give you a 100% positive yes or no, but it can give you like 99.99% positive
and it takes like 1% of the time
i dunno how it works, ipquarx does it ask him

well i could avoid calling the sqrt function in the for loop because ive heard its costly to call functions in for loops a lot.

Lugnut · February 21, 2014, 01:27:05 PM

Jesus I didnt even see that
Get that stuff out of there, that's a HUGE slowdown

Ipquarx · February 21, 2014, 01:40:18 PM

Quote from: Lugnut on February 21, 2014, 01:13:33 PM

it can't give you a 100% positive yes or no, but it can give you like 99.99% positive
and it takes like 1% of the time
i dunno how it works, ipquarx does it ask him

There's a lot of maths involved, but basically, by the time you can check the first 10k or so primes with that algorithm you can check with 1/10¹⁰⁰ precision that a number is or is not a prime.
I've never actually successfully implemented it myself but I'll definitely let you know.

Quote from: Blockzillahead on February 21, 2014, 01:25:48 PM

well i could avoid calling the sqrt function in the for loop because ive heard its costly to call functions in for loops a lot.

oh god yeah, might wanna remove that.

On top of that there are faster ways to do trial division even, like for example using the fact that every prime > 3 can be represented as 6n+1 or 6n-1 instead of 2n+1 removes a lot of useless iterations.

Unrelated: on Tuesday I'm participating in a programming contest organize by the University of Waterloo!

Blockzillahead · February 21, 2014, 01:46:51 PM

Quote from: Lugnut on February 21, 2014, 01:27:05 PM

Jesus I didnt even see that
Get that stuff out of there, that's a HUGE slowdown

checked this out;
http://www.codeproject.com/Articles/465041/Primality-Test
both functions;

Code: [Select]

bool * primalitycheck(long long number)
{
    bool * prime = new bool[number + 1];
    for(int i = 0; i <= number; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
    int squareRoot = sqrt(number);
    for(int i = 2; i <= squareRoot; i++)
    {
        if(prime[i])
        {
            for(int j = 2*i; j <= number; j += i)
            {
                prime[j] = false;
            }
        }
    }
    return prime;
}

bool isPrime(long long number)
{
    if(number < 2)
        return false;
    if(number == 2)
        return true;
    if(number%2 == 0)
        return false;
    for(int i = 3; i <= sqrt(number); i += 2)
    {
        if(number%i == 0)
            return false;
    }
    return true;
}

then checked up to 1000000 to see which executes faster

Code: [Select]

#include <iostream>
#include <cmath>
#include <ctime>

bool * primalitycheck(long long number)
{
    bool * prime = new bool[number + 1];
    for(int i = 0; i <= number; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
    int squareRoot = sqrt(number);
    for(int i = 2; i <= squareRoot; i++)
    {
        if(prime[i])
        {
            for(int j = 2*i; j <= number; j += i)
            {
                prime[j] = false;
            }
        }
    }
    return prime;
}

bool isPrime(long long number)
{
    if(number < 2)
        return false;
    if(number == 2)
        return true;
    if(number%2 == 0)
        return false;
    for(int i = 3; i <= sqrt(number); i += 2)
    {
        if(number%i == 0)
            return false;
    }
    return true;
}
int main()
{
    long long number = 1000000;
    bool * primes;
    primes = primalitycheck(number);
    std::clock_t startfunction1;
    double function1;
    startfunction1 = std::clock();
    for(int i = 0; i < number; i++)
    {
        if(primes[i])
        {
            std::cout << i << " ";
        }
    }
    function1 = ( std::clock() - startfunction1 ) / (double)CLOCKS_PER_SEC;

    //Second part
    std::clock_t startfunction2;
    double function2;
    startfunction2 = std::clock();
    for(int i = 0; i < number; i++)
    {
        if(isPrime(i))
        {
            std::cout << i << " ";
        }
    }
    function2 = ( std::clock() - startfunction2 ) / (double)CLOCKS_PER_SEC;
    std::cout <<"\nfirst: "<< function1;
    std::cout <<"\nsecond: "<< function2 <<'\n';
    return 0;
}

the new one wins

Quote

first: 10.656
second: 12.688

there has to be faster ways than 10 seconds. how do those banks find huge primes that have like 30+ digits? do they generate them over time, store them and use them after?

Quote from: Ipquarx on February 21, 2014, 01:40:18 PM

Unrelated: on Tuesday I'm participating in a programming contest organize by the University of Waterloo!

good luck

edit:
someone made a function thats a bit faster than the first one from above

Code: [Select]

bool IsPrimeOptimizationFour(int number)
{
	if (number < 2) return false;
	if (number == 2) return true;
	if (number == 3) return true;
	if (number == 5) return true;
	if (!(number % 2)) return false;
	if (!(number % 3)) return false;
	if (!(number % 5)) return false;
	if (number < 7*7) return true;
	int step[] = {7,11,13,17,19,23,29,31};
	int sentry = (int)sqrt((double)number);
	for(int r = 0; r < sentry; r += 30)
            for(int i = 0; i < 8; ++i)
                if (!(number % (r+step[i])))
                    return false;
	return true;
}

its faster by a few milliseconds also its a pretty clever algorithm

Port · February 21, 2014, 02:08:56 PM

so many special cases

Steve5451� · February 21, 2014, 02:14:36 PM

Quote from: Port on February 21, 2014, 02:08:56 PM

so many special cases

You're a special case.

Starzy · February 21, 2014, 02:21:15 PM

Quote from: Steve5451² on February 21, 2014, 02:14:36 PM

You're a special case.

lol

Ipquarx · February 21, 2014, 03:05:12 PM

Quote from: Blockzillahead on February 21, 2014, 01:46:51 PM

how do those banks find huge primes that have like 30+ digits? do they generate them over time, store them and use them after?

It's called the Miller-Rabin primality test.

It's what's known as a probabilistic test; meaning that there is a change that the algorithm is actually wrong.
In the case of this algorithm: If it returns that the number is not a prime, then it is guaranteed to not be a prime. If it returns true, that it is a prime, then there's actually a very small chance that it isn't a prime and is composite.

The thing about it is that the chance is very small, to be exact there's a 1/4^k chance that it's wrong, where k is the number of times you run the test. This means that if you run the test 10 times then there's a one in one million chance that it's not a prime, if you run it 20 times that means there's a one in one trillion chance that the number isn't a prime.

Please note that in order for modular exponentiation to work, the variable type you're using has to be able to hold the entirety of the number modulus * modulus without overflow.

And I actually just got it working now in C#, it's absolutely blazingly fast.

And thanks for the good luck :)

Blockzillahead · February 21, 2014, 03:08:20 PM

Quote from: Ipquarx on February 21, 2014, 03:05:12 PM

And I actually just got it working now in C#, it's absolutely blazingly fast.

the rsa system?