Faster way of getting the factorial in mysql

[fredreload]

So I created a MYSQL database and attempted to store the factorial values, it took me an entire night to get to 10000. Suggestions needed, maybe multithreading with database insertion, is that possible?

static private void ConnectAndQuery()
        {

            using (var connection = new MySql.Data.MySqlClient.MySqlConnection("Server=localhost;Database=factorial;Uid=root;Pwd=freeloader;"))
            using (var command = connection.CreateCommand())
            {
                connection.Open();

                command.CommandText = "insert into table1(valf) values(@fac)";
                command.Parameters.Add("@fac", "1");

                BigInteger mult = 1;
                for (int i = 1; i < 1000000; i++)
                {

                    Console.WriteLine(i);

                    mult *= i;

                    command.Parameters["@fac"].Value = mult;
                    command.ExecuteNonQuery();
                }

                command.CommandText = "select idf, valf from table1";

                using (var reader = command.ExecuteReader())
                    while (reader.Read())
                        Console.WriteLine(reader.GetString(0) + ": " + reader.GetString(1));
            }

        }

[Strange]

Have you checked how long it takes to retrieve a data item from mySQL, compared with storing it in an array, compared with calculating it?

[fredreload]

No, but storing it in an array would lose it the next time you run the program. You're gonna keep it in a text? But calculating is the slowest. Well, what is your idea Strange?

Edited October 11, 2016 by fredreload

[Strange]

My guess is that storing the values in a (binary) file and using that to initialise an array when the program starts, would be fastest.

[fredreload]

Hmm, I'm gonna work with the database first, I'm going to do a 1000000! then divide 1000000 and back until 1 to get the list. It should be fast

 

 

P.S. You are free to test out the array method though, if you need the code just let me know, if you are in the mood to test it out that is

P.S. Nevermind it's taking a long time writing the values into the database

Need a fast way to insert large text to MYSQL, or something that can create value in DB like PLSQL

Edited October 11, 2016 by fredreload

[Mordred]

speed up the divide operations with bit shifts. In binary multiplcation/division by two is faster using bit shift left/right operations. Remember you have the tools of binary and hexadecimal math.

Edited October 11, 2016 by Mordred

[fredreload]

speed up the divide operations with bit shifts. In binary multiplcation/division by two is faster using bit shift left/right operations. Remember you have the tools of binary and hexadecimal math.

Division and multiplication is fast, I can get to 1 million factorial with no problem. The problem is inserting it as a text string into the database takes time and that is what I am looking into, faster way of insert large text strings.

[Mordred]

ah gotcha, Nothing I really had to worry about for the programming I do. I'm more PLC based languages. So can't really help

Edited October 12, 2016 by Mordred

[Klaynos]

You may well be limited by the disk write speed. Get a faster disk?

 

Not sure if mysql can do it but some dbs can be run entirely in the ram of the computer. That's my normal approach to speeding up db readwrite.

[fredreload]

I'm doing insert from Visual Studio C#, I'm wondering if there is a script on MYSQL workbench that would generate the same thing and be faster. I'm thinking something like PL/SQL from Oracle, but whether it is faster I cannot say

 

 

P.S. MYSQL has stored procedure

P.S. Stored procedure can't handle large value multiplication and sql got too slow at around 50000!, what should I do?

Edited October 12, 2016 by fredreload

[Sensei]

I'm doing insert from Visual Studio C#, I'm wondering if there is a script on MYSQL workbench that would generate the same thing and be faster. I'm thinking something like PL/SQL from Oracle, but whether it is faster I cannot say

 

 

P.S. MYSQL has stored procedure

P.S. Stored procedure can't handle large value multiplication and sql got too slow at around 50000!, what should I do?

Check if you're compiling in Debug mode,

if so, change it to Release mode.

It should be working faster.

 

Also,

learn how to insert multiple rows in single SQL command.

http://stackoverflow.com/questions/6889065/inserting-multiple-rows-in-mysql

or LOAD DATA

http://dev.mysql.com/doc/refman/5.7/en/load-data.html

 

Check this article. Guy said he had 1000 insert operations per second (in PHP), and managed to get 28000 per second after optimizations.

http://kvz.io/blog/2009/03/31/improve-mysql-insert-performance/

Edited October 12, 2016 by Sensei

[fredreload]

Check if you're compiling in Debug mode,

if so, change it to Release mode.

It should be working faster.

 

Also,

learn how to insert multiple rows in single SQL command.

http://stackoverflow.com/questions/6889065/inserting-multiple-rows-in-mysql

or LOAD DATA

http://dev.mysql.com/doc/refman/5.7/en/load-data.html

 

Check this article. Guy said he had 1000 insert operations per second (in PHP), and managed to get 28000 per second after optimizations.

http://kvz.io/blog/2009/03/31/improve-mysql-insert-performance/

Well my problem is not inserting the number of rows, but each row has like 50000! number of text strings. 50000! numbers in 1 insert. So my problem is on how to insert a large chunk of data at once, but not inserting multiple rows

Edited October 13, 2016 by fredreload

[Klaynos]

How much delay are you getting?

 

Even if each sting us a single byte that is 50kB. With a disk speed of 80MB/s that is around half a second. If the strings are 4 bytes you have 2 seconds of delay...

[fredreload]

How much delay are you getting?

 

Even if each sting us a single byte that is 50kB. With a disk speed of 80MB/s that is around half a second. If the strings are 4 bytes you have 2 seconds of delay...

I ran it for an entire night and the computer restarted at factorial 34729. It takes around 1 second to insert 2 records at this point. If database method does not work then maybe there is a way to improve computing speed? Or maybe multithreading.

[Sensei]

Check CPU usage in Task Manager, if there is just 12.5% used on f.e. Core i7 8 HT threads,

split to various threads.

1st thread will be working on (x+0)!

second on (x+1)!

third on (x+2)!

etc. up to (x+thread_count-1)!

then x+=thread_count in each thread.

 

I am usually using BackgroundWorker

https://msdn.microsoft.com/en-us/library/system.componentmodel.backgroundworker(v=vs.110).aspx

as it allows me for update GUI periodically, and cancellation.

Edited October 13, 2016 by Sensei

[Klaynos]

My experience is mostly on Linux.

 

My work involves millions of data points each with several bits of unique metadata. You need to really understand what resource you're using to optimise. I use very quick disks on boxes with 40 cores and more than 200GB ram. Without understanding when to split into multiple cores and when not is critical else you end up just filling up the ram as the processes split off and everything grinds to a halt as you start using swap.

[fredreload]

My experience is mostly on Linux.

 

My work involves millions of data points each with several bits of unique metadata. You need to really understand what resource you're using to optimise. I use very quick disks on boxes with 40 cores and more than 200GB ram. Without understanding when to split into multiple cores and when not is critical else you end up just filling up the ram as the processes split off and everything grinds to a halt as you start using swap.

I'll post a newer version of my code here later and see if you want to run it for me. I'll try a new multithreading methods, possibly this one

Edited October 14, 2016 by fredreload

[fredreload]

First let me explain what my program is doing. To begin with, consider a data with 15, 1 bits and 15, 0 bits. It can be an image, a game, or any file.

 

Let's assume this is my data 101010101010101010101010101010, I will have it arranged into 000000000000000111111111111111.

 

Why do I re-arrage it? Because the data can now be remember as 15 0's 15 1's with the number 15 where I summed up the bits instead of typing 000000000000000 and 111111111111111. It is now stored as a sum of base 10 number.

 

Now the important thing is the number n it takes to get from 101010101010101010101010101010 to 000000000000000111111111111111 which takes binary permutation. I chose this number because this is the worst case for 30 bits, 30 choose 15. If you have 30 1's or 30 0's it's simply 30 choose 30 which makes n=1 so that it only takes 1 number to get to the desired output.

 

The number n can be found with the solution from Staphen I posted in this forum. The good thing is this number n will always be less than the actual number. Keep in mind n is a large number.

 

Now that we've acquired the number n and the 15 0's and 15 1's, it's time to find the original data. But before we do this we can further shrink the number n.

 

Let's assume n is one hundred which is 1100100 in binary, we find how far it is away from 0000111 and find the n again.

 

The result is an array of zeros, ones, and the final number n.

It's a really good algorithm, just doesn't work on large files for now. Anyway, have fun, and don't break your hard drive!

 

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Threading.Tasks;
using System.Text;

namespace HelloWorld
{
class Hello
{
public static byte[] bytes = System.IO.File.ReadAllBytes(@"C:\Data\star.jpg");

public static byte[] bytes_new;

static void Main()
{

StringBuilder sb = new StringBuilder();
/*
for (int k = 0; k < bytes.Length; k++)
{
sb.Append(Convert.ToString(bytes[k], 2));
}

sb.Clear();
sb.Append("10101011");
*/
BigInteger nb = new BigInteger(bytes.Concat(new byte[] { 0 }).ToArray());

bytes_new = nb.ToByteArray();


for (int i = 0; i < bytes_new.Length; i++)
{
sb.Append(Convert.ToString(bytes_new, 2).PadLeft(8, '0'));
}

Console.WriteLine(sb);
Console.WriteLine();



int[] one = new int[50];
int[] zero = new int[50];
int[] position = new int[50];


for (int i = 0; i < 50; i++)
{

for (int j = 0; j < sb.Length; j++)
{
char c = sb[j];
if (c == '0')
{
zero++;
}
else
{
one++;
}
}


//one = IteratedBitcount(number_compress);
//zero = IteratedZerocount(number_compress);
position = one + zero;

BigInteger fac = Factorial(one);

BigInteger n = FindN(sb, one, position, fac);


sb = ToB(n,sb);



//sb.Append(string.Join("",n.ToByteArray().Select(x => Convert.ToString(x, 2).PadLeft(8, '0'))));

Console.WriteLine(sb);
Console.WriteLine();


}

//Console.WriteLine(number_compress);
//Console.WriteLine();

/*
for (int i = 0; i < 15-1; i++)
{
one = one - one[i+1];
position = position - position[i + 1];
}
*/

BigInteger number_decompress = 0;

for (int i = 50 - 1; i >= 0; i--)
{

BigInteger fac = Factorial(one);

number_decompress = FindNumber(sb, one, position, fac);

sb = ToB(number_decompress, sb);

//sb.Append(string.Join("",number_decompress.ToByteArray().Select(x => Convert.ToString(x, 2).PadLeft(8, '0'))));
Console.WriteLine(sb);
Console.WriteLine();
}

//Console.WriteLine(number_decompress);
Console.WriteLine();



byte[] final = new byte[sb.Length / 8];

for (int i = sb.Length/8-1; i >= 0; i--)
{
final = Convert.ToByte(sb.ToString(i*8, 8),2);
}

BigInteger b = new BigInteger(final);

bytes_new = b.ToByteArray();

//byte[] buffer = Encoding.ASCII.GetBytes(sb.ToString());

File.WriteAllBytes(@"C:\Data\new_star.jpg", bytes_new);

}

static StringBuilder ToB(BigInteger n,StringBuilder sb)
{
sb.Length = 0;
sb.Capacity = 0;
sb.Clear();

int num = 0;
while (BigInteger.Pow(2, num) <= n)
{
num++;
}

for (int k = num - 1; k >= 0; k--)
{
BigInteger counter = BigInteger.Pow(2, k);
if (n >= counter)
{
sb.Append("1");
n = n - counter;
}
else
{
sb.Append("0");
}

}

return sb;
}

static string ToBinaryString(BigInteger bigint)
{
var bytes = bigint.ToByteArray();
var idx = bytes.Length - 1;

// Create a StringBuilder having appropriate capacity.
var base2 = new StringBuilder(bytes.Length * 8);

// Convert first byte to binary.
var binary = Convert.ToString(bytes[idx], 2);



// Ensure leading zero exists if value is positive.
if (binary[0] != '0' && bigint.Sign == 1)
{
base2.Append('0');
}


// Append binary string to StringBuilder.
base2.Append(binary);

// Convert remaining bytes adding leading zeros.
for (idx--; idx >= 0; idx--)
{
base2.Append(Convert.ToString(bytes[idx], 2).PadLeft(8, '0'));
}

return base2.ToString();
}

static BigInteger FindNumber(StringBuilder sb, int one, int position, BigInteger fac)
{
BigInteger number = 0;
BigInteger n = 0;
int k = one;

for (int l = 0; l < sb.Length; l++)
{
if (sb[l] == '1')
{
n = n + BigInteger.Pow(2, sb.Length-l-1);
}
}

for (int j = position - 1; j >= 0; j--)
{
BigInteger mult = j;
BigInteger num = 0;

for (int i = 1; i < (int)k; i++)
{
mult *= (j - i);
}


num = (mult / fac);



if (num <= n)
{
number = number + BigInteger.Pow(2, j);
fac /= k;
k--;
n = n - num;
}
//Console.WriteLine(k);
if (k == 0)
break;
}
return number;
}

static BigInteger FindN(StringBuilder sb, int one, int position, BigInteger fac)
{
/*
BigInteger findMSB = number;
BigInteger test = number;
BigInteger MSB = 1;
while (findMSB > 0)
{
MSB <<= 1;
findMSB >>= 1;
}
MSB >>= 1;
*/

BigInteger n = 0;
int k = one;
int pos = position;

for (int i = 0; i < sb.Length; i++)
{
if (sb == '1')
{
int a = pos - 1;
BigInteger mult = a;

for (int j = 1; j < k; j++)
{
mult *= (BigInteger)(a - j);
}

n += (mult / fac);

fac /= k;
k--;

}
//Console.WriteLine(k);
if (k == 0)
break;
pos--;

}
return n;
}

static int IteratedBitcount(BigInteger n)
{
BigInteger test = n;
int count = 0;

while (test != 0)
{
if ((test & 1) == 1)
{
count++;
}
test >>= 1;
}
return count;
}

static int IteratedZerocount(BigInteger n)
{
BigInteger test = n;
int count = 0;

while (test != 0)
{
if ((test & 1) == 0)
{
count++;
}
test >>= 1;
}
return count;
}

static BigInteger Factorial(int arg)
{
BigInteger value = 1;
for (int index = 2; index <= arg; index++)
{
value *= index;
}
return value;
}


}
}

P.S. Tested on 1016 bits = =, if you want to run bigger files like 1MB, you will need to improve this algorithm or use a super computer

P.S. By the way, I think you can shrink the keys

Edited October 14, 2016 by fredreload

[Strange]

I wonder if you would be better off looking at the concept of Hamming distance rather than combinatorials...

https://en.wikipedia.org/wiki/Hamming_distance

[fredreload]

Hmm, the actual run for a 43 byte file generated 58 byte of storage. This wouldn't work unless you can predict the nth value. Kind of a pain. The nth value sequence goes like this 1, 5, 21, 69, 469, 2135, 16921, 84593.

[fiveworlds]

If database method does not work then maybe there is a way to improve computing speed?​

 

 

Using Rom, Cache etc yeah but that is up to manufacturers.