24
\$\begingroup\$

Problem 8 on Project Euler which asks

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the product?

This is my solution in Visual C#.

class ProblemEight
    {
        static byte[] input = new byte[] { 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0 };
        static long product, max = 0;
        public static void SolutionEight()
        {
            for (short i = 0; i < 987; i++)
            {
                product = (long)input[i]
                    * input[i + 1]
                    * input[i + 2]
                    * input[i + 3]
                    * input[i + 4]
                    * input[i + 5]
                    * input[i + 6]
                    * input[i + 7]
                    * input[i + 8]
                    * input[i + 9]
                    * input[i + 10]
                    * input[i + 11]
                    * input[i + 12];
                max = product > max ? product : max;
            }
            Console.WriteLine(max);
        }

    }

It gives the correct answer and it's best run time out of 20,000 runs in the release build has been 0.0956389122543305 milliseconds on an Intel Core i5-5200U @2.2Ghz processor.

How can I speed it up further?

[BENCHMARK]

Here are the benchmarks of all the awesome solutions provided in the answers. The implementations were run on an Intel Core i5-5200U @2.2Ghz processor with 8GB RAM. The fastest time was calculated out of 20,000 runs and Console.WriteLine(...) was not called in any implementation.

NOTE: I've tried my best to run all implementation on same standards without introducing my own optimizations (string to int conversions for the input were removed wherever necessary)

JNS' Bitshift optimization

  • x64 (Debug) - 0.241196671392629 milliseconds
  • x64 (Release) - 0.131561820759616 milliseconds

Forsvarir's multi-threaded optimization

  • x64 (Debug) - 0.0797768487584903 milliseconds
  • x64 (Release) - 0.070446223172702 milliseconds

Risky Martin's reciprocal multiplication (implemented by brian_o)

  • x64 (Debug) - 0.0121298132615248 milliseconds
  • x64 (Release) - 0.0181947198922873 milliseconds

Dennis_E's Queue optimization

  • x64 (Debug) - 0.033590252108838 milliseconds
  • x64 (Release) - 0.0284584080366544 milliseconds

Falco's Dividend-Factor multiplication

  • x64 (Debug) - 0.0149290009372613 milliseconds
  • x64 (Release) - 0.00793103174792009 milliseconds

Domi1819's Casting optimization

  • x64 (Debug) - 0.0102636881443672 milliseconds
  • x64 (Release) - 0.005598375351473 milliseconds

Brian_o's Meticulous Zero-skip

  • x64 (Debug) - 0.00933062558578834 milliseconds
  • x64 (Release) - 0.00419878151360475 milliseconds

Zonker.in.Geneva and Mathreadler's Logarithmic approach (implemented by brian_o)

  • x64 (Debug) - 0.0121298132615248 milliseconds
  • x64 (Release) - 0.00466531279289417 milliseconds

[UPDATE]

If you are looking for a larger dataset to test your algorithm, I've generated 1 million random numbers using George Marsaglia's CMWC (Complementary Multiply With Carry) Generator (source code here).

Here is the File

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Are you allowed to use parallel processing? \$\endgroup\$
    – Der Kommissar
    May 18, 2016 at 9:20
  • 1
    \$\begingroup\$ Isn't the point of project Euler that you figure this out for yourself? projecteuler.net/about \$\endgroup\$
    – Dominic Cronin
    May 18, 2016 at 11:59
  • 6
    \$\begingroup\$ I've already completed the Euler challenge. Correct solution in under a second (I reached 0.9ms) But interested to see how far it can be optimized \$\endgroup\$
    – Paras
    May 18, 2016 at 12:09
  • 1
    \$\begingroup\$ Remember to compile and benchmark as both x86 and x64. You may get surprising results. \$\endgroup\$
    – brian_o
    May 18, 2016 at 21:26
  • 5
    \$\begingroup\$ This is not the first Project Euler question on Code Review. Actually if you check this tag project-euler you can see more of them. Additionally, the purpose of naming the question with Project Euler is so people are aware what they are looking and not accidently spoil themselves, because honestly if one wants to look for the solution they are already here on the internet. The "project euler: x" helps those who don't want to spoil themselves of the answer. You can read more about it here \$\endgroup\$
    – Paras
    May 19, 2016 at 12:04

12 Answers 12

Reset to default
8
\$\begingroup\$

Inspired by Zonker.in.Geneva and mathreadler's ideas.

This doesn't do any multiplying or dividing to find the correct index. Only at the very end, when it has found the best run, it calculates that runs product.

    private static readonly byte[] logs = { 0, 0, 69, 109, 138, 160, 179, 194, 207, 219 };
    public static long SolutionEightAlt19()
    {
        int bestScore = 0;
        uint bestIndex = 0;

        int runningScore = 0;
        uint prevUsable = 0;

        for (uint i = 0; i < 1000; ++i)
        {
            if (input[i] == 0)
            {
                prevUsable = 0;
                runningScore = 0;
            }
            else
            {
                ++prevUsable;
                runningScore += logs[input[i]];
                if (prevUsable > 13) runningScore -= logs[input[i - 13]];
                if (prevUsable >= 13 && runningScore > bestScore)
                {
                    bestScore = runningScore;
                    bestIndex = i - 12;
                }
            }
        }
        return (long)(input[bestIndex] * input[bestIndex + 1] * input[bestIndex + 2] * input[bestIndex + 3] * input[bestIndex + 4] * input[bestIndex + 5] * input[bestIndex + 6]) * (input[bestIndex + 7] * input[bestIndex + 8] * input[bestIndex + 9] * input[bestIndex + 10] * input[bestIndex + 11] * input[bestIndex + 12]);
    }
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ +1: This was my idea also, though you might be able to further improve it with if (input[i] == 0) { .. i = i+12; } \$\endgroup\$
    – RBarryYoung
    May 19, 2016 at 18:43
  • \$\begingroup\$ Hmm, my i+12 doesn't work at all because it still has to load the pipline. duh. My bad, you got it right. \$\endgroup\$
    – RBarryYoung
    May 20, 2016 at 18:27
  • \$\begingroup\$ This one clocks out at 0.0713792857312808 milliseconds on my machine! Interesting solution \$\endgroup\$
    – Paras
    May 21, 2016 at 1:37
  • \$\begingroup\$ All of the answers are great but I'm picking this one because it's very inspiring and possibly scalable with minor effort! Thanks everyone \$\endgroup\$
    – Paras
    May 26, 2016 at 22:00
  • \$\begingroup\$ How did you pick the scale for the logarithm approximations? According to the back of my envelope, 255 for log(9) is barely accurate enough for 13 digits, 219 is dangerously inaccurate, and 130 happens to show the lowest relative error of all 8-bit scale values. \$\endgroup\$
    – greybeard
    Apr 6, 2019 at 17:42
18
\$\begingroup\$

Using your base algorithm with a timing unit I get an average of 130 ticks (0.013 milliseconds) per iteration. (Note: running on Debug)

class ProblemEight
{
    static byte[] input = { 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0 };
    static long product, max = 0;
    static long[] timings = new long[1000];

    public static void SolutionEight()
    {
        Stopwatch watch = new Stopwatch();

        for (int iterations = 0; iterations < timings.Length; iterations++)
        {
            watch.Restart();

            for (short i = 0; i < 987; i++)
            {
                product = (long)input[i]
                    * input[i + 1]
                    * input[i + 2]
                    * input[i + 3]
                    * input[i + 4]
                    * input[i + 5]
                    * input[i + 6]
                    * input[i + 7]
                    * input[i + 8]
                    * input[i + 9]
                    * input[i + 10]
                    * input[i + 11]
                    * input[i + 12];
                max = product > max ? product : max;
            }

            watch.Stop();
            timings[iterations] = watch.ElapsedTicks;
        }

        Console.WriteLine(timings.Average());
    }
}

Skipping zeros

if (input[i + 12] == 0)
    i += 13;

Skipping zeros after setting the new max value gets it down to ~60 ticks (0.006 milliseconds).

This is covered in most of the other answers, but it's a very significant performance improvement that shouldn't be omitted. Check the other answers for better explanations.

Optimizing multiplication

product = (long)(input[i] * input[i + 1] * input[i + 2] * input[i + 3] * input[i + 4] * input[i + 5] * input[i + 6])
    * (input[i + 7] * input[i + 8] * input[i + 9] * input[i + 10] * input[i + 11] * input[i + 12]);

By simply adding two pairs of braces, you can get it down to ~30 ticks (0.003 milliseconds) per operation. Magic, huh?

In .NET, multiplying two bytes will not return a byte. In fact, all integer multiplications in .NET will result in an int, as long as there are no longs involved. (If there is a long involved, both sides will be casted to long and a "long multiplication" is performed)

In your code, long multiplications are done (since 9^13 can overflow an int the idea is correct) however long multiplication is less performant than int multiplication. In your sample 12 long multiplications are performed.

The idea behind this optimization is to split the multiplication into smaller parts, specifically into blocks of 6 and 5 int multiplications (since 9^7 can not overflow ints) and then doing a final long multiplication to gain performance.

Other optimizations that I could think of did not provide any significant improvement.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Wow, that was very astute pointer! * 0 * \$\endgroup\$
    – Paras
    May 18, 2016 at 12:55
  • 1
    \$\begingroup\$ I've reached 0.0643813165419395 milliseconds just by applying these two simple refactors! Thanks \$\endgroup\$
    – Paras
    May 18, 2016 at 13:00
7
\$\begingroup\$

Implementing a shifting frame approach where you just divide by the leading digit and multiply by the last instead of multiplying all 13 digits over and over again is unfortunately not a good approach for 13 digits. Division is usually much slower on arithmetic units than multiplication (I remember a factor of 10-15 for some CPUs) so a single division might be slower than 13 multiplications. So I tried a different approach: I just multiply the dividends and factors and wait unti all the multiplied factors are bigger than the dividends and only then do a division and multiplication.

And I skip zeroes.

You could implement some shifting frame logic like this:

Let a product p_i be the product of all digits d_i...d_(i+1)
A product p_(i+1) can only be bigger than p_i if the digit d_(i+13) is bigger than d_i
Because: p_(i+1) = p_i / d_i * d_(i+13)

So you can skip the multiplication if the next digit is smaller or equal. This could make the algorithm twice as fast...

You can expand this, by multiplying the divisor_digits divs = d_i * d_(i+1)... and multiplying the new digits prods = d_(i+13) * d_(i+14) and only calculate the new maximum if prods > divs, then the new maximum is p_i / divs * prods

Results are the same as the original implementation and runtime is about 3-4 times faster in a first benchmark.

Java-Code:

private static long shiftingFrame( final int[] input )
{
    final long cutoff = Long.MAX_VALUE / 10;
    final int totalDigits = input.length;

    int i = skipZeroes( input, 0, 13 );
    long maxprod = i < totalDigits ? multiplyDigits( input, i ) : 0;
    long lastprod = maxprod;

    i = i + 12;

    long diffactor = 1;
    long mults = 1;

    for ( ++i; i < totalDigits; ++i )
    {
        final int digit = input[ i ];
        if ( digit == 0 )
        {
            i = skipZeroes( input, i, 13 );
            if ( i >= totalDigits )
            {
                break;
            }

            lastprod = multiplyDigits( input, i );
            i = i + 12;
            mults = 1;
            if ( lastprod >= maxprod )
            {
                maxprod = lastprod;
                diffactor = 1;
            }
            else
            {
                diffactor = maxprod / lastprod;
            }

        }
        else
        {
            final int spareDigit = input[ i - 13 ];

            mults *= digit;
            diffactor *= spareDigit;

            if ( mults > diffactor || diffactor > cutoff )
            {
                lastprod = multiplyDigits( input, i - 12 );
                mults = 1;
                if ( lastprod > maxprod )
                {
                    maxprod = lastprod;
                    diffactor = 1;
                }
                else
                {
                    diffactor = maxprod / lastprod;
                }
            }
        }
    }

    return maxprod;
}

private static long multiplyDigits( final int[] input, final int start )
{
    return (long) ( input[ start ] * input[ start + 1 ] * input[ start + 2 ] * input[ start + 3 ]
            * input[ start + 4 ] * input[ start + 5 ] * input[ start + 6 ] )
            * ( input[ start + 7 ] * input[ start + 8 ] * input[ start + 9 ] * input[ start + 10 ]
                    * input[ start + 11 ] * input[ start + 12 ] );
}

private static int skipZeroes( final int[] input, int start, final int digits )
{
    final int length = input.length;
    int end = start + digits;

    for ( int i = start; i < end; ++i )
    {
        if ( i >= length )
        {
            return length;
        }

        if ( input[ i ] == 0 )
        {
            start = i + 1;
            end = start + digits;
        }
    }

    return start;
}
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Over the thumb Benchmark timings in Java: Orginal: 14,5 ms, ZerroSkipping: 11,5 ms and ShiftFrame: 4,3 ms (Average runtime over a loop with 100.000, and warmup: 10.000 rounds) - Benchmarking code: pastebin.com/R4uvgRNP \$\endgroup\$
    – Falco
    May 18, 2016 at 11:27
  • \$\begingroup\$ I converted the code to C# (had to remove all the finals) and the algorithm's fastest clocked out at 0.0779107236413326 milliseconds! It's awesome! \$\endgroup\$
    – Paras
    May 18, 2016 at 12:35
  • 1
    \$\begingroup\$ I have made some more benchmarks and robustness-tests, I have changed the code a little and added a check for long-overflow, which could occur with high numbers. It is now safer and still as fast, if you want to use the code, please update these changes :-) - I am also trying around with other data-types, sometimes floating point arithmetics are faster than long calculations... \$\endgroup\$
    – Falco
    May 18, 2016 at 14:09
  • \$\begingroup\$ Great! Keep us updated. Try if you can simplify the nested structures, maybe use a more lightweight data type (memory access is faster) \$\endgroup\$
    – Paras
    May 18, 2016 at 14:37
6
\$\begingroup\$

One obvious optimisation would be to skip sections that have a 0 in them. In the code below, I'm checking if the 13th digit is a 0 and if so, skipping the next 13 numbers, their product is always going to be 0...

int i = 0;
do
{
    product = (long)input[i]
        * input[i + 1]
        * input[i + 2]
        * input[i + 3]
        * input[i + 4]
        * input[i + 5]
        * input[i + 6]
        * input[i + 7]
        * input[i + 8]
        * input[i + 9]
        * input[i + 10]
        * input[i + 11]
        * input[i + 12];
    max = product > max ? product : max;
    if (0 != input[i + 12]) i++;
    else i += 13;
}
while (i < 987);

On a modern cpu, you can gain some benefit from parallel execution. Since the number of executions required is quite small, you need to avoid starting/ending threads however as this can have quite an overhead so you want to use threads from the thread pool. You also want to minimise contention between the threads, so you don't want them all updating the same Max variable. A basic strategy is to split the processing into a number of sections (where the number of sections is the number of CPUs).

Each window, calculates the max for that window, then compares it with the max for the other windows. The calculation stage can then but opitimised using the various other techniques suggested.

This results in code something like the following (I haven't really validated the upper bounds checking however it does result in the correct answer so I've assumed it is close enough).

public static void SolutionEight()
{
    var threads = Environment.ProcessorCount;
    int windowSize = 1000 / threads;
    var tasks = new Task<long>[threads];
    for (int i = 0; i < threads; i++)
    {
        int windowStart = i;
        tasks[windowStart] = Task<long>.Run(() => { return GetMax(windowStart * windowSize, (windowStart + 1) * windowSize - ((windowStart == threads - 1) ? 12 : 0)); });
    }
    long max = 0;
    foreach (var task in tasks)
    {
        var result = task.Result;
        max = max > result ? max : result;
    }
    Console.WriteLine(max);

}

static public long GetMax(int start, int end)
{
    long max = 0;

    for(int i = start; i < end - 12; i++)
    {
        if (HasZero(i)) continue;
        // Optimised as suggested by @Falco
        if (i > 0 && input[i - 1] > input[i + 12]) continue;

        // Optimised as suggestd by @domi1819
        long product = (long)(input[i]
            * input[i + 1]
            * input[i + 2]
            * input[i + 3]
            * input[i + 4]
            * input[i + 5]
            * input[i + 6])
            *( input[i + 7]
            * input[i + 8]
            * input[i + 9]
            * input[i + 10]
            * input[i + 11]
            * input[i + 12]);

        max = product > max ? product : max;
    }


    return max;
}

static bool HasZero(int i)
{
    return !(input[i] != 0 &&
           input[i + 1] != 0 &&
           input[i + 2] != 0 &&
           input[i + 3] != 0 &&
           input[i + 4] != 0 &&
           input[i + 5] != 0 &&
           input[i + 6] != 0 &&
           input[i + 7] != 0 &&
           input[i + 8] != 0 &&
           input[i + 9] != 0 &&
           input[i + 10] != 0 &&
           input[i + 11] != 0 &&
           input[i + 12] != 0);
}
Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ What if the number at index i+13 is also 0? Is that a risk we must take or is there a way around that as well? \$\endgroup\$
    – Paras
    May 18, 2016 at 8:23
  • 1
    \$\begingroup\$ @ParasDPain When the 13th digit is 0, you could go into an if that scans until it gets 13 digits that don't have 0. Whether or not it's worth while would depend on the number of 0s within 13 digits of each other. There's the same risk at the start of the set of numbers, although obviously you can visually check that this doesn't exist for the specific problem. \$\endgroup\$
    – forsvarir
    May 18, 2016 at 8:34
  • \$\begingroup\$ That's a very extreme solution! I love it! Was waiting for a thread based implementation. \$\endgroup\$
    – Paras
    May 18, 2016 at 13:13
  • \$\begingroup\$ The fastest run of your implementation clocked at 0.159553697516981 milliseconds. I tried removing the for and linearize the code but only got upto 0.14695... milliseconds \$\endgroup\$
    – Paras
    May 18, 2016 at 14:14
  • \$\begingroup\$ @ParasDPain interesting, I get about a 50% boost over your original solution, but I'm running on a fairly old i7 laptop. It may be that your CPU is running through the code to quickly, so the cost of threading is higher than the cost of execution. \$\endgroup\$
    – forsvarir
    May 18, 2016 at 14:25
6
\$\begingroup\$

I implemented Risky Martin's proposal of using reciprocal multiplication, and it seems to be my best performer so far. Who knew?

I was kind of surprised because I thought that performing 1.0 / input[i - 13] (a division) would be just as expensive as dividing, but maybe there's an optimization because one is a long and the other is a byte? Voodoo? Or maybe I'm just wrong?

When generalizing, be careful for precision errors, but it seems fine for this particular input.

    public static long SolutionEightAlt8()
    {
        double best = 0;
        double prevProduct = 1;

        uint prevUsable = 0;
        for (uint i = 0; i < 1000; ++i)
        {
            if (input[i] == 0)
            {
                prevUsable = 0;
                prevProduct = 1;
            }
            else
            {
                ++prevUsable;
                prevProduct *= input[i];
                if (prevUsable > 13)
                {
                    double recip = 1.0 / input[i - 13];
                    prevProduct *= recip;
                }
                best = prevProduct > best ? prevProduct : best;
            }
        }
        return (long)best;
    }
Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Reciprocal is not just a division. There are faster ways to compute them than dividing the number 1.0 by them and we need to cast the "input[i]" to double although the compiler probably does that for you if you have not switched on your pedantic flags. But good contribution anyway. Compile with "-Ofast" should do such numerical short cuts automatically but can also destroy precision. \$\endgroup\$
    – mathreadler
    May 18, 2016 at 17:29
  • \$\begingroup\$ Really interesting idea, however this is still (a tiny tiny bit) slower than my implementation on my current hardware (not the same I used for the benchmarks of my answer) Benchmark Code. \$\endgroup\$
    – Domi
    May 18, 2016 at 17:40
  • \$\begingroup\$ I was thinking you could store the reciprocals in an array, so there would be no division in the loop. So you could write something like prevProduct *= reciprocals[input[i - 13]]; It's interesting that calculating the reciprocal in the loop is faster than just dividing in the loop. \$\endgroup\$
    – Risky Martin
    May 19, 2016 at 0:40
  • \$\begingroup\$ @RiskyMartin I actually tried that in a subsequent experiment and was VERY surprised to learn that it didn't make a difference! Since there are only 10 possible digits, I baked a precomputed "here's the reciprocal for any digit" right into the class as a static readonly array. But no change! Maybe it gets cached in some way? \$\endgroup\$
    – brian_o
    May 19, 2016 at 1:07
  • \$\begingroup\$ Since division is exact (dividing two integers to produce an integer), you should use 2adic division rather than real division. I assume long does arithmetic modulo 2^64? The presence of even divisors makes things a bit more complicated than usual; what you can do is make your table satisfy inverse[y] * y == 8 (mod 2^64). Then, to divide x by y, you can do your arithmetic with long and compute (x * inverse[y]) >> 3. \$\endgroup\$
    – user14393
    May 19, 2016 at 17:32
5
\$\begingroup\$

Skipping 0s is good, but really you want to make sure none of your 13 consecutive digits is 0.

In your example data, starting at index 157, you have the following string of digits (874715852386305071569329096329522744304355766896648) which I've split up into runs of 0s and non-0s:

874 715 852 386 3 (13 digits)

0

5

0

715 693 29

0

963 295 227 443 (12 digits)

0

435 576 689 664 8 (13 digits)

By only skipping the first 0 (because digits[i+13] == 0), you're performing 24 unnecessary calculations, all of which equal zero.

Also, once you confirm that none of the 13 consecutive digits is 0, then if digits[i+13] == 1, you can skip over it, because either the product is the same (if digits[i] == 1) or less (if digits[i] > 1).

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I'm expanding on the Skipping Zeroes section listed above, trying to optimize it further....Sorry if i wasn't clear. But, i did see (after I posted) that brian_o is already on that path \$\endgroup\$
    – Zonker.in.Geneva
    May 18, 2016 at 17:05
4
\$\begingroup\$

Here's one that does the unrolled multiplication and also does 0 sequence skipping. I made a similar function that did division and a single multiplication, but this one is faster.

BTW, I liked the readability of your original.

    public static long SolutionEightAlt3()
    {
        long best = 0;

        uint prevUsable = 0;
        for (uint i = 0; i < 1000; ++i)
        {
            if (input[i] == 0)
            {
                prevUsable = 0;
            }
            else
            {
                ++prevUsable;
                if (prevUsable >= 13)
                {
                    long prevProduct = (long)(input[i - 12] *
                                              input[i - 11] *
                                              input[i - 10] *
                                              input[i - 9] *
                                              input[i - 8] *
                                              input[i - 7]) *
                                       (long)(input[i - 6] *
                                              input[i - 5] *
                                              input[i - 4] *
                                              input[i - 3] *
                                              input[i - 2] *
                                              input[i - 1] *
                                              input[i]);
                    best = prevProduct > best ? prevProduct : best;
                }
            }
        }
        return best;
    }

EDIT (More reasoning):

One way to think about solution is to say that there are 988 substrings, and you need to find the best one.

Calculating the score for a substring at index i has a certain cost. If you can optimize that cost, great. (see domi1819's answer, or my original (late to the party!).

It's worth it to think about whether you can shortcut the cost of a given index i's cost by using i-1 to bootstrap the cost caluclation: divide by the non-shared "old" digit, multiply by the "new" digit. In my experiments, with my hardware, I found that calculating the score outright (non-bootstrap, 13 optimized number multiplication) outperformed the divide-and-multiply methodology. So I'm sticking with the 13-num-multiply method. But the important part is, I checked! If we were looking for 26-digit strings, the answer would almost certainly be different.

Your first method did 987 scorings. But as others have talked about, the presence of zeroes makes many of those calculations unnecessary.

So figuring out which scorings can be obviated is very important, BUT there's a tradeoff: zero-skipping is not free!

  • no zero skipping: 987 scorings
  • domi1819: (CHEAP zero skipping methodology!) 430 scorings for this input
  • my solution: (more expensive zero skipping methodology) 263 scorings for this input

On my hardware, my method seems to perform better than domi1819's, and I believe it's because I'm doing fewer scorings. I've been playing around with the algorithm and trying to do cheaper zero-skipping. My best implementation so far is 330 scorings with even faster overall performance than my currently posted answer. I feel there's still some room for improvement.

You mentioned parallelization. Might be a good strategy, but remember, just like zero skipping it's not free! I have yet to run experiments, but sounds like fun. My gut tells me it wouldn't be worth it with input this small, but who knows! Measure!

Final Edit:

I think I've gone as far as I'm willing to go. This is my final, best-performing function (for this input, using my hardware, compiling to x86). It does some zero skipping (moderate cost), and ends up computing 330 scores. My other more sophisticated attempts to compute fewer scores haven't outperformed it, maybe because they spend too much time figuring out what not to compute, or maybe because they mess up cache lines. Who knows.

    public static long SolutionEightAlt15()
    {
        long best = 0;
        for (uint i = 0; i < 988; ++i)
        {
            long product = (long)(input[i    ] * input[i + 1] * input[i + 2] * input[i + 3 ] * input[i + 4 ] * input[i + 5 ] * input[i + 6]) *
                                 (input[i + 7] * input[i + 8] * input[i + 9] * input[i + 10] * input[i + 11] * input[i + 12]);
            best = product > best ? product : best;
            if (product == 0)
            {
                // skip forward. you might still be inside an invalid region, but 
                // you'll just end up skipping forward again. decent balance of cost
                // and efficacy for the tested input
                uint j;
                for (j = 12; j >= 0; --j)
                {
                    if (input[i + j] == 0) break;
                }
                i += j;
            }
        }
        return best;
    }
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Thanks and I like the iterative checker for consecutive 0s . Also, is it necessary to explicitly cast the long twice, wouldn't once suffice? \$\endgroup\$
    – Paras
    May 18, 2016 at 13:17
  • 1
    \$\begingroup\$ @ParasDPain I'm pretty sure it's unnecessary, but I don't think it costs anything at runtime. I also think it helps readability by making intention clear. (If I learned it actually DOES cost something at runtime, I'd remove it.) \$\endgroup\$
    – brian_o
    May 18, 2016 at 14:02
  • \$\begingroup\$ Actually, the IL code of (long)int1 * int2 casts both ints to longs. When there's a long on one side, the compiler decides to cast other side to long as well to perform a long multiplication. \$\endgroup\$
    – Domi
    May 18, 2016 at 16:10
  • 2
    \$\begingroup\$ Yes, and you can confirm it yourself by disassembling long l = (long)int1 * int2;, which results in ldloc.X (load variable X onto stack), conv.i8 (cast stack top to long), ldloc.Y (load variable Y onto stack), conv.i8 (cast stack top to long), mul (multiply two top stack elements and store result on stack) and stloc.Z (store stack top into variable Z and remove stack top). As you can see it's doing two casts although you only told it to cast the left side. \$\endgroup\$
    – Domi
    May 18, 2016 at 16:41
3
\$\begingroup\$

One optimization is to use bitshift for numbers that are multiple of 2. Not sure if that is significant, but in therory it should be faster ;). The code example below has also a few structual optimizations:

public class ProblemEight
{
    static readonly long[] input = new long[] { 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0 };

    const int ADJACENT_DIGITS_LENGTH = 13;

    public static void SolutionEight()
    {
        var max = 0L;
        for (short i = 0; i < input.Length - ADJACENT_DIGITS_LENGTH; i++)
        {
            var product = 1L;
            for (int j = 0; j < ADJACENT_DIGITS_LENGTH; j++)
            {
                var val = input[i + j];
                switch (val)
                {
                    case 1:
                        break;
                    case 2:
                        product <<= 1;
                        break;
                    case 4:
                        product <<= 2;
                        break;
                    case 8:
                        product <<= 3;
                        break;
                    default:
                        product *= val;
                        break;
                }
            }
            max = product > max ? product : max;
        }
        Console.WriteLine(max);
    }
}

Edit: Added the case 1 in code above.

Maybe it is also possible to let the compiler optimize the code. That requires the compile to know the concrete number at compile time:

switch(val)
{
    case 2:
        product *= 2;
        break;
    case 3:
        product *= 3;
        break;
    //...
}
Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ I ran the solution with the same clocking mechanism, and out of 20,000 runs the fastest took 0.181480667643583 milliseconds . The bit shifts must've made it faster but the 2nd for loop slows it down as well. Can you elaborate on if var is faster and the use of Math.Max(...), etc. \$\endgroup\$
    – Paras
    May 18, 2016 at 6:47
  • \$\begingroup\$ var doesn't have any effect of performance because it is actually a long (the compiler knows that it must be a long). I think Math.Max(...) has also no effect on performance... but i didn't checked it. \$\endgroup\$
    – JanDotNet
    May 18, 2016 at 6:52
  • 1
    \$\begingroup\$ @ParasDPain: You are right... the nested for loop slows it down (I am fixed to optimize code for readablity that I didn't see it ^^). Therefore another optimization would be to remove the first for loop. That could be done by using T4 templates. \$\endgroup\$
    – JanDotNet
    May 18, 2016 at 6:55
  • 2
    \$\begingroup\$ There is no difference between using var or the explicity type because it results in the same compilation. \$\endgroup\$
    – JanDotNet
    May 18, 2016 at 7:10
  • 2
    \$\begingroup\$ @ParasDPain That's a different question (and one which has many answers round the network). \$\endgroup\$
    – Philip Kendall
    May 18, 2016 at 10:17
3
\$\begingroup\$

One optimization is to skip sequences that contain a 0. Another is if the previous sequence doesn't start with a 0, calculate the current sequence by dividing the previous product by first digit in the previous sequence and multiplying by the last digit in the current sequence.

I hope you had code to convert the 1000 digits from the string into an array of digits. I know you're going for speed, but a lot of times readability and maintainability is more important, and in those cases you'd want to calculate a product using loops or LINQ instead of coding an increment to the index 13 times. You should also calculate the currently hardcoded value of 987 using something like int count = input.Count() - sequenceLength;.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Agreed, I'm currently trying to implement the skip for 0 and the frame-shifting to reduce multiplication operations. Agreed readability is important but I'm competing with friends so ready to sacrifice it. And yes of course I wrote a function to convert the string to a byte array \$\endgroup\$
    – Paras
    May 18, 2016 at 8:36
  • 4
    \$\begingroup\$ I'm not sure if a shifting frame will be a benefit, in many Arithmetic Units division is about 10-15 times slower than multiplication, which would make the single division maybe more expensive than 13 multiplications... but you can test it... \$\endgroup\$
    – Falco
    May 18, 2016 at 9:08
  • \$\begingroup\$ I'll test and post results \$\endgroup\$
    – Paras
    May 18, 2016 at 9:30
  • 2
    \$\begingroup\$ @ParasDPain Instead of dividing, you could also try storing the reciprocals of the digits in an array and multiplying them or using a corresponding multiply shift operation. \$\endgroup\$
    – Risky Martin
    May 18, 2016 at 10:39
3
\$\begingroup\$

You are basically doing all multiplications 13 times.
When you have the product of 13 numbers, a1 * a2 * ... * a13, all you have to do to find the next product is divide by a1 and multiply by a14. You don't have to multiply a2 through a13 all over again.
The obvious way to handle this is by using a Queue.

The 2nd optimization you can make is to start a new sequence of 13 when you encounter a 0. (If you don't check for 0, you'll get a DivideByZeroException)

First, let's make an extension method to get all the digits from a number-string:

public static IEnumerable<int> Digits(this string s) {
    foreach (char c in s) yield return c - '0';
}

Then solve problem 8:

public long SolveProblem008() {
    private const string input = "731..."; //I'm not going to display the entire string here...

    return GreatestConsecutiveProduct(13, input.Digits());
}

static long GreatestConsecutiveProduct(int length, IEnumerable<int> digits) {
    var buffer = new Queue<int>(length);
    long product = 1L, max = long.MinValue;
    foreach (int input in digits) {
        if (buffer.Count < length) { //We don't have 13 digits yet
            if (input == 0) { //Encountered a 0: start from scratch
                product = 1L;
                buffer.Clear();
            } else {
                buffer.Enqueue(input);
                product *= input;
            }
        } else {
            if (input == 0) { //Encountered a 0: start from scratch
                product = 1L;
                buffer.Clear();
            } else {
                product /= buffer.Dequeue();
                buffer.Enqueue(input);
                product *= input;
                if (product > max) max = product;
            }
        }
    }
    return max;
}
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I ran it and am getting the wrong answer - 2090188800 (possibly an overflow, the max product exceeds int.MaxValue). Could you please confirm that \$\endgroup\$
    – Paras
    May 18, 2016 at 10:18
  • \$\begingroup\$ And it was, I changed the type of the method, product and Queue to long and got the correct answer but still the fastest run of 20,000 runs only reached 0.122231195173827, tells me the implementation can be improved \$\endgroup\$
    – Paras
    May 18, 2016 at 10:21
  • \$\begingroup\$ @ParasDPain Yes, I forgot. The problem used to be to find a sequence of 5 consecutive numbers (if I remember correctly) which fits well within an int. They changed it to 13 later. I edited it to return a long \$\endgroup\$
    – Dennis_E
    May 18, 2016 at 10:24
  • 3
    \$\begingroup\$ This optimization will help for very large n (>13), but on most arithmetic unit division is much slower (factor 10-15) than multiplication. So a single division will probably be slower than 13 multiplications. And this is without taking pipelining, branch prediction and L1/L2 caches into account... \$\endgroup\$
    – Falco
    May 18, 2016 at 10:47
  • 1
    \$\begingroup\$ Have you actually tested this and found that it improves performance? This seems.. most unlikely really. As Falco says the optimisation itself is more than questionable for the number of digits we're talking about, but the real problem is the horribly unpredictable branch you have in there. And that's just the two major things - the overhead from the queue probably won't matter too much, but is far from free anyhow. \$\endgroup\$
    – Voo
    May 18, 2016 at 13:24
3
\$\begingroup\$

Seems someone had already tried my first instinct to make a "moving frame" that divides an old number in the tail and multiplies a new in the front (1mul and 1 div instead of 12 mul). However divs are more slow than muls and also screw up the pipelines so maybe that is why it did not work very well.

Another popular approach in engineering is to do dyadic subdivision, calculate pairs of products, then pairs of those and so on.

So first level would be the original numbers n1,n2,n3,.... Second level would be n1*n2,n3*n4,... third level n1*n2*n3*n4,.... and so on. We can stop at 8 since that will be the power of two which is just below 13.

So the first product will be "first eight * third four * 13th number". In best case two multiplications instead of 12. I can leave the implementation as an exercise, after all the project is aimed to help people get better at programming.

I just realized I have no way to test this. Even current state of my unoptimized code with optimization flags takes only 7-17 µs to run, which is far too little to do any reliable testing. Maybe if we can come up with some mockup data which is a lot longer so it forces every algorithm to take longer.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I'll post 1 million random number sequence in the question to benchmark algorithm's efficiency with data size \$\endgroup\$
    – Paras
    May 21, 2016 at 3:13
  • 1
    \$\begingroup\$ Sounds great. Maybe post a link to a file instead of all the number in the question text. \$\endgroup\$
    – mathreadler
    May 21, 2016 at 3:29
  • \$\begingroup\$ I've updated the question with a link to the file (sorry about the delay) \$\endgroup\$
    – Paras
    May 21, 2016 at 14:40
2
\$\begingroup\$

I had another thought which is a variation on the shifting frame...

The problem with the shifting frame idea is that division is much slower than multiplication.

But...the 13 consecutive digits that determine the maximum product are also the same consecutive digits that determine the maximum SUM....

So, if we employ the shifting frame method but subtract the first element and add the next element, we avoid divisions. We only keep track of the index which will give us the greatest sum. At the end of our loop, we do one single multiplication based on 13 consecutive digits starting at the GreatestSumIndex.

Naturally, we still want to avoid any sequences that have any zeros.

As it's approaching 02:00am, I'll work on the code in the morning. Unless someone else wants a stab at it....

Improve this answer
\$\endgroup\$
7
  • 6
    \$\begingroup\$ "the 13 consecutive digits that determine the maximum product are also the same consecutive digits that determine the maximum SUM" Unfortunately, nope. 5555555555555 has a smaller digit sum than 9191919191916, but its digit product is way bigger. \$\endgroup\$
    – brian_o
    May 19, 2016 at 2:29
  • 3
    \$\begingroup\$ It will work with a log law though $\log(ab) = log(a)+log(b)$, but sadly most ways of calculating logs is rather slow. \$\endgroup\$
    – mathreadler
    May 19, 2016 at 15:56
  • 3
    \$\begingroup\$ mathreadler You only need to calculate the log of each digit once. \$\endgroup\$
    – user1008646
    May 19, 2016 at 17:03
  • \$\begingroup\$ Yes I agree, but that calculation can still be slow. I read in other stackexchange and overflow sites that c implementations of log can take 35 cycles on modern intel cpus where a multiplication would only take a few or less than one in average if there is a good pipeline. But maybe it's worth it if it's only once per digit. \$\endgroup\$
    – mathreadler
    May 21, 2016 at 4:19
  • \$\begingroup\$ @mathreadler You can make this work without doing any log calculations at runtime. Throw the log representation of digits 1-9 into a static array. \$\endgroup\$
    – brian_o
    May 22, 2016 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.