trjhtr

So, this is my problem to solve:

I want to calculate $2^n$ where $0 < n< 10000$

I am representing each element of array as a space where 4digit number should be "living" and if extra digit appears, I am replacing it to the next element of this array.

The principle I am using looks like this:

The code I am using is the following:

static string NotEfficient(int power)

if (power < 0)
 throw new Exception("Power shouldn't be negative");
if (power == 0)
 return "1";
if (power == 1)
 return "2";

int A = new int[3750];

int current4Digit = 0;

//at first 2 is written in first element of array
A[current4Digit] = 2;

int currentPower = 1;

while (currentPower < power)

 //multiply every 4digit by 2
 for (int i = 0; i <= current4Digit; i++)
 
 A[i] *= 2;
 

 currentPower++;

 //checking every 4digit if it
 //contains 5 digit and if yes remove and 
 //put it in next 4digit
 for (int i = 0; i <= current4Digit; i++)
 
 if (A[i] / 10000 > 0)
 
 int more = A[i] / 10000;
 A[i] = A[i] % 10000;
 A[i + 1] += more;

 //if new digit should be opened
 if (i + 1 > current4Digit)
 
 current4Digit++;
 

 


 


//getting data from array to generate answer
string answer = "";

for (int i = current4Digit; i >= 0; i--)

 answer += A[i].ToString().PadLeft(4,'0') + ",";


return return answer.TrimStart('0');

How I can make this algorithm better?

Here's how I would make your algorithm better.

First: your principle is sound. You are displaying a large binary number in base 10 by taking advantage of the fact that int already has a method that displays a 32 bit number in base 10. Essentially your method is:

• convert the number to base 10000, by making an int array "digits" from 0 to 9999.


• Make a device which can double one of those numbers


• Print the result after the given number of doublings.

This technique works, but your implementation could use some improvements. The improvements I would make are:

• Go big! Why base 10000? You could do base 100000000 in an int no problem or base 1000000000000000000 in a long. Let's do that.


• You allocate a huge number of ints. That's probably either way too many or way too few for the problem at hand. Don't limit yourself. Make a solution that grows as you need it, not one that has an arbitrary limit. Moreover: you make 3750 ints, but you could do the entire problem with only 167 longs.


• Abstract away your operations into a type that represents the value


• Refactor each part of the algorithm into a helper method that does one thing well.


• Stop using mutable state. It's OK to burn a little memory. The garbage collector will deal.


• Use a more efficient algorithm to calculate big powers.

How might we put these principles into practice? Let's try.

First off, I'm going to make a struct which represents a number encoded in base 1000000000000000000. Its implementation will be a list of longs, but it could be any collection type. Lists are just convenient.

(Aside: Why a struct? The implementation is small; it's a wrapper around a single reference. The meaning of the struct is logically a value. It is immutable. So this is a good candidate for a value type. We get the benefits of having a clean interface and implementation hiding, but we only pay the price of a single reference.)

struct Base1000000000000000000
{
 private List<long> digits;
 private Base1000000000000000000(List<long> digits) 
 this.digits = digits;
 

Note that so far everything is private. I want this to have a very locked-down interface. We've got to get this party started somewhere, so let's represent one:

 public static readonly Base1000000000000000000 One = 
 new Base1000000000000000000(new List<long> 1L );

You could do Zero similarly.

Now what does our display algorithm look like? That's a one-liner:

public override string ToString() =>
 string.Join("",
 ((IEnumerable<long>)digits)
 .Reverse()
 .Select(d => d.ToString().PadLeft(18, '0')));

Note that we're using the non-destructive reverse, not the destructive reverse on list.

The core of the algorithm is in our adder, which takes a number and returns its double:

 public Base1000000000000000000 DoubleIt() 
 
 // Note, _ separators in constants are new for C# 7.
 const long TheBase = 1_000_000_000_000_000_000;
 var result = new List<long>();
 result.Add(0);
 for (int i = 0; i < this.digits.Count; i += 1)
 
 // Make sure we have storage.
 if (i == result.Count)
 result.Add(0);
 result[i] += this.digits[i] + this.digits[i];
 // We might have to carry.
 if (result[i] >= TheBase)
 
 // Again, make sure we have room.
 if (i + 1 == result.Count)
 result.Add(0);
 result[i+1] = result[i] / TheBase;
 result[i] -= TheBase;
 
 
 // And we're done.
 return new Base1000000000000000000(result);
 

Super. Now the main algorithm is straightforward:

Base1000000000000000000 c = Base1000000000000000000.One;
for (int i = 0; i < n; ++i)
 c = c.DoubleIt();
return c.ToString();

Notice how when I extract each operation to its own method, the code becomes simpler and more elegant.

Now, how can you improve this further?

• 
  Exercise: (Easy) Implement operator+ on this type.


• 
  Exercise: (Pretty Easy) Implement operator- on this type, and represent negative numbers correctly.


• 
  Exercise: (Hard) Implement operator* on this type.


• 
  Exercise: (Very hard) Now that you have multiplication and addition, you can get to 2ⁿ much faster. Suppose you want to do 2³⁸⁴. Start with One. Double it. Now you have 2¹. Multiply it by itself -- square it. Now you have 2². Square it again to get 2⁴. Square it again to get 2⁸. And so on, until you have them up to 2²⁵⁶. Multiply 2²⁵⁶ by 2¹²⁸ to get 2³⁸⁴, and you're done. Your original algorithm does 384 doublings, but you can get the answer with one doubling and nine multiplies. Can you work out the algorithm for the optimal sequence of multiplications and additions?


• 
  Exercise (Very hard): Implement % and / on this type.


• 
  Exercise (Very very hard): Now do it all over again without using any built-in type for the math. (Obviously use string for the text.) You are leveraging the ability of int or long to represent a bitfield that can be displayed in base 10. What if you didn't have that? Because someone had to write that code. The person who wrote that code didn't have it because it hadn't been written yet. Suppose C# didn't have any integer type; how would you implement math from scratch?