The 2nd Monitor

« first day (1161 days earlier) ← previous day next day → last day (2857 days later) »

Mathias Ettinger

11:01 PM

It's getting really late in here, TTGTB

Phrancis

@MathiasEttinger Good night!

So much space wasted with those C# braces on the next line ;P

Mast

@Phrancis Ah, close enough.

Phrancis

Got a PrimeFactorization method working but my first try is kinda slow, because it's pretty bute force-ish

            //This works but is a little slow
//            while(!IntUtils.IsPrime(number))
//            {
//                foreach(var p in primes)
//                {
//                    if(number % p == 0)
//                    {
//                        yield return p;
//                        number /= p;
//                        break;
//                    }
//                }
//            }

Pretty sure it's that foreach

N3buchadnezzar

@Phrancis Pls stahp

My eyes.

It hurts precious

Phrancis

That method took 601ms to PrimeFactorize 100,000

Not good

N3buchadnezzar

11:09 PM

@Phrancis A 235 sieve is heaps faster

Generating primes first to get the factorization is generally a bad idea.

Phrancis

I have a super-fast prime generation utility method though

N3buchadnezzar

@Phrancis Does it run faster if you change the if loop to a while loop?

Phrancis

Annnnd now I'm getting out of range again :|

    //Alternate method
    var i = 0;
    while(!IntUtils.IsPrime(number))
    {
        while(number % primes[i] == 0)
        {
            yield return primes[i];
            number /= primes[i];
        }
        i++;
    }

Captain Obvious

Q: Parallel Sum Scan using CUDA

I'm learning CUDA (and C to some extent), and one of the algorithms that I am learning is the Hillis-Steele scan algorithm. I wrote a program that performs a simple scan with adding. I don't really care that the random number generation is in serial; this is just educational. #include "cuda_run...

N3buchadnezzar

@Phrancis Java right?

Phrancis

11:15 PM

Ugh, my alternate method is slower :'(

I fixed the OOR though, by changing i++ to ++i

        //Alternate method
        var i = 0;
        int divisor;
        while(!IntUtils.IsPrime(number))
        {
            Console.WriteLine("i = {0}", i);
            divisor = primes[i];
            while(number % divisor == 0)
            {
                yield return divisor;
                number /= divisor;
            }
            ++i;
        }

Although, let me take out the WriteLine

Eh, about the same

Nope, not fixed

Screw it, going back to the other one

N3buchadnezzar

@Phrancis There are really 4-5 big factorization algorithms that is used.

Q: How can I improve this Pollard's rho algorithm to handle products of semi-large primes?

Below is my implementation of Pollard's rho algorithm for prime factorization: #include <vector> #include <queue> #include <gmpxx.h> // Interface to the GMP random number functions. gmp_randclass rng(gmp_randinit_default); // Returns a divisor of N using Pollard's rho method. mpz_class getDiv...

c++ algorithm prime-factoring

Here is an implementation of the naive Pollard rho algorithm. Works well for small ish numbers. So numbers less than about 1000036317378699858851366323.

Phrancis

For some values of small-ish o.O

N3buchadnezzar

@Phrancis Large numbers are in the range 256-1024 bits :p

27bits is nothing.

Phrancis

That's insane

N3buchadnezzar

@Phrancis The algorithm which is fastest is this one. en.wikipedia.org/wiki/Quadratic_sieve

Or it is tied with the en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization

However even with a master in mathematics the quadratic sieve is totally greek for me :p

Phrancis

11:27 PM

Uh, ok, and I am supposed to try to implement it!?

N3buchadnezzar

@Phrancis Pollard Brent should be doable =)

I linked to an implementation in C++ as well as two explenations. It is basically just some clever use of gcd and modulo

Phrancis

I suppose prime numbers have been at the core of discrete mathematics for ages, must be why there are so many ways of doing the same things

N3buchadnezzar

@Phrancis As well as being extremely important in internet security.

Phrancis

They use those for encryption and things like that right?

N3buchadnezzar

It might be a good thing that your algorithm sucks. Otherwise every encryption key and bank transfer could be broken and hacked.

Phrancis

11:34 PM

LOL

Captain Obvious

Q: Using argparse module within cmd interface

I've created an application that uses a cmd interface. It has multiple levels, and the number of available commands and their complexity is growing. As such, I need to generalise argument parsing - of the line parameter. I like argparse - I've previously used it a few times for its 'intended' p...

python

N3buchadnezzar

@Phrancis Yeah. You can read about the RSA algorithm if you want. Basically if you want to decode the message you would have to factor really big primes.