Potega 2 - przyspieszenie algorytmu

Mam problem z tym wbrew pozorom łatwym zadaniem na SPOJU.
http://pl.spoj.pl/problems/POW2/

Zakres wyniku wyklucza możliwość użycie przesunięć bitowych. Trzeba używać stringów. std::string jest za wolny, więc użyłem statycznej tablicy charów. Pospłaszczałem pętle jak się dało, niemal wszystkie operacje arytmetyczne zastąpiłem logicznymi, nie ma żadnych mnożeń. Niestety dalej nie mieszczę się w czasie. skleciłem coś takiego:

 
#include <stdio.h>

int main()
{
    short int k,x,rozmiar=1;
    bool czydodac,dwucyfrowa;
    char s[4933];

    while(scanf("%hd",&x)!=EOF)
    {

        s[1]=0;
        s[0]='1';rozmiar=1;

        if (x!=0)
        for(short int j=0;j<x;j++)   //liczba mnożeń przez 2 (wykładnik potegi)
        {
            czydodac=false;dwucyfrowa=false;
            for (short int i=0;i<rozmiar;i++)   //"mnożenie" każdej cyfry w tablicy przez 2
            {
                if (s[i]>=54) dwucyfrowa=true;
                if ((s[i]=='1')||(s[i]=='6')) s[i]='2'; else
                if ((s[i]=='2')||(s[i]=='7')) s[i]='4'; else
                if ((s[i]=='3')||(s[i]=='8')) s[i]='6'; else
                if ((s[i]=='4')||(s[i]=='9')) s[i]='8'; else
                if ((s[i]=='5')||(s[i]=='0')) s[i]='0';

                if (czydodac==true) {s[i]++;czydodac=false;}

                if(dwucyfrowa==true) czydodac=true;

                dwucyfrowa=false;

            }

            if (czydodac==true)       //jak iloczyn pierwszej cyfry jest większy od 10 to wpisuję 1 na początek
            {
                s[rozmiar]='1';
                rozmiar++;
            }
        }

        for(int i=rozmiar-1;i>=0;i--) printf("%c",s[i]);          //wynik od tyłu
        printf("\n");

    }
    return(0);

}

Coś się zarejestrować na forum u nich nie mogę toteż pytam tutaj, może ktoś robił i mi da jakąś wskazównę na szybszy algorytm

nie rób obliczeń na char ale na tablicy unsigned int, niech każda komórka unsigned int reprezentuje pseudo cyfrę 0-999999999 (10⁹-1). Potem będziesz drukował te liczby jako segmenty liczby wyniku.

swoją drogą ten twój kod jest podejrzanie krótki.
wiem nawet czemu, nie zastosowałeś algorytmu szybkiego potęgowania.

W systemie dziesiętnym jak mnożysz przez 10 to przesuwasz tylko przecinek - wykorzystaj to w podnoszeniu 1 << x :)

algorytm robiący to, co potrzebujesz, dla x = 16383 (największa liczba wynikająca z założeń) na moim i7 średnio 45ms. niestety w c#, bo mam wstręt do c i c++

class test
{
	static readonly ulong max = (ulong)System.Math.Pow(10, (uint)(System.Math.Floor(System.Math.Log10(ulong.MaxValue)))-1);

	static void mul2(ref ulong[] tab, ref int len)
	{
		bool carry = false;
		for (int i = 0; i < len; i++)
		{
			tab[i] <<= 1;
			if (carry) tab[i]++;
			if (carry = (tab[i] >= max)) tab[i] -= max;
		}
		if (carry) tab[len]++;
		if (tab[len] > 0) len++;
	}

	static void Main(string[] args)
	{
		int x = 16383;
		var tab = new ulong[1 + (uint)(System.Math.Ceiling((float)x * System.Math.Log(2, max)))];
		int len = 1;
		tab[0] = 1;

		for (int i = 0; i < x; i++)
			mul2(ref tab, ref len);

		for (int i = len-1; i >= 0; i--)
			System.Console.Write(tab[i]);
		System.Console.WriteLine();
	}

}

wersja działająca na byte zamiast ulong również mieści się poniżej sekundy, ale to już na styk.