[Systemy liczbowe][Algorytmy] Podnoszenie do szóstej potęgi

[KazikWielki]

Witam! Mam zadanie: Ile razy musisz wykonać mnożenie, aby obliczyć wartość wyrażenia \(\displaystyle{ x ^{6}}\)? Pięć razy? Wystarczy wykonać trzy razy, skorzystaj w tym celu z przedstawienia \(\displaystyle{ 6 = 2 \cdot 3}\). Podaj inny sposób obliczania szóstej potęgi, polegający na wykonaniu również tylko trzech działań mnożenia, który wynika z rozwinięcia liczby 6 w systemie dwójkowym.

W pierwszym podpunkcie będzie oczywiście \(\displaystyle{ \left( x ^{2} \right) ^{3}}\), natomiast nie przychodzi mi nic do głowy z tym rozwinięciem binarnym liczby 6 (0110). Naprowadzi mnie ktoś?

[Medea 2]

Słyszałeś może o binarnym potęgowaniu liczb? Działa nie tylko dla szóstki. jak zwykle zawiera artykuł na ten temat.

[KazikWielki]

Nie mogą być użyte żadne pętle ani instrukcje warunkowe.

[kicaj]

\(\displaystyle{ 6=2^2 +2}\) więc \(\displaystyle{ a^6 =a^{2^2 +2 } = (a^2 )^2 \cdot a^2}\)

[KazikWielki]

@kicaj Nie o to chodzi (mają być 3 działania mnożenia, u ciebie są 4), ale dzięki wszystkim za pomoc. Sam już doszedłem

[Medea 2]

Czyżbyś liczył \(\displaystyle{ x^2}\), potem \(\displaystyle{ x^2 \cdot x}\) i wreszcie \(\displaystyle{ (x^2 \cdot x)^2}\)?

[ksisquare]

Kod: Zaznacz cały

#define X(n,w) double x##n = w;
 
static double swpow(double x, int n) {
    switch (n)    {
        case 0: { return ( 1.0 ); }  // 0
        case 1: { return ( x ); }  // 0
        case 2: { return ( x * x ); }  // 1
        case 3: { return ( x * x * x ); }  // 2
        case 4: { X(2,x*x) return( x2 * x2 ); }  // 2
        case 5: { X(2,x*x) return( x2 * x2 * x ); }  // 3
        case 6: { X(2,x*x) return( x2 * x2 * x2 ); }  // 3
        case 7: { X(3,x*x*x) return( x3 * x3 * x ); }  
        case 8: { X(2,x*x) X(4,x2*x2) return( x4 * x4 ); }
        case 9: { X(3,x*x*x) return( x3 * x3 * x3); }
        case 10:{ X(2,x*x) X(4,x2*x2) return( x4 * x4 * x2 ); }
        case 11:{ X(2,x*x) X(4,x2*x2) return( x4 * x4 * x2 * x ); }
        case 12:{ X(2,x*x) X(6,x2*x2*x2) return( x6*x6 ); }
        case 13:{ X(2,x*x) X(4,x2*x2) X(8,x4*x4) return( x8 * x4 *x ); }
        case 14:{ X(3,x*x*x) X(7,x3*x3*x) return( x7*x7 ); }
        case 15:{ X(3,x*x*x) X(6,x3*x3) return( x6*x6*x3 ); }
        case 16:{ double x2=x*x; x2*=x2; x2*=x2; return( x2 * x2 ); }
        case 17:{ X(2,x*x) X(4, x2*x2) X(8,x4*x4) return( x8*x8*x ); }
        case 18:{ X(2,x*x) X(4, x2*x2) X(8,x4*x4) return( x8*x8*x2 ); }  // 5
        case 19:{ X(2,x*x) X(4, x2*x2) X(8,x4*x4) return( x8*x8*x2*x ); }  // 6
        case 20:{ X(2,x*x) X(3,x2*x) X(5, x2*x3) X(10,x5*x5) return( x10*x10 ); }  // 5
        case 21:{ X(3,x*x*x) X(6,x3*x3) X(15,x6*x6*x3); return( x15*x6 ); }
        case 22:{ X(2,x*x) X(4,x2*x2) X(11,x4*x4*x2*x ) return( x11*x11 ); }  // 6
        case 23:{ X(2,x*x) X(3,x2*x) X(5, x2*x3) X(10,x5*x5) return( x10*x10*x3 ); }  // 6
        case 24:{ X(2,x*x) X(6,x2*x2*x2) X(12,x6*x6); return( x12*x12 ); }  // 5
        case 25:{ X(2,x*x) X(4, x2*x2) X(8,x4*x4) X(17,x8*x8*x); return( x17*x8 ); }  // 6
        case 26:{ X(2,x*x) X(4,x2*x2) X(8,x4*x4) X(13,x8*x4*x) return( x13*x13 ); }  // 6
        case 27:{ X(2,x*x) X(3,x2*x) X(6,x3*x3) X(12,x6*x6) return( x12*x12*x3 ); }  //  6
        case 28:{ X(3,x*x*x) X(7,x3*x3*x) X(14,x7*x7) return( x14*x14 ); }  // 6
        case 29:{ return( pow( x, n ) ); }
        case 30:{ X(3,x*x*x) X(6,x3*x3) X(12,x6*x6) return( x12*x12*x6 ); }  // 6
        case 31:{ return( pow( x, n ) ); }
        case 32:{ X(2,x*x) X(4,x2*x2) X(8,x4*x4) X(16,x8*x8) return( x16*x16 ); }  // 5
        default:{ return( pow(x, n) ); } } }

potęgowanie szybsze niż szybkie