Каков алгоритм вывода на экран больших чисел после возведения в степень?

Question

Вводится k - основание, n - показатель, нужно вывести k^n в символьном массиве-строке(char string[]), как мне выводить гигантское число(например 3^100), если я не могу записать его в переменную?

Answer 1

Большие числа надо уже заносить в массив цифр. И вручную выполнять математические действия. Возведение в степень числа k можно упростить, если число хранить в k-ой системе счисления. Тогда результатом будет "круглое" число:

k^n = "1000...00"

где количество нулей будет равно n.
Дальше для вывода нужно преобразовать из k-ой системы исчисления в десятичную.
Алгоритм взят у Stanislav Volodarskiy у ответа Система счисления на с++ (закрыт)

// gcc -Wall -Wextra -Wpedantic -Winline -Wshadow -Wconversion -std=c11 -Os степень.c -o степень
// echo 100 100 | ./степень
# include <stdio.h>
# include <stdlib.h>
typedef struct vec_int vec_int ;

// number = factor * number + term
void mul_add( int factor, int term, vec_int * const number ) ;
void vec_int_init ( vec_int * ) ;
void vec_int_push_back ( vec_int * , int ) ;
void vec_int_free ( vec_int * ) ;

struct vec_int {
  int * arr ;
  int size ;
  int memsize ;
} ;

static inline unsigned long int int_cast_ulong ( int const i ) {
  return ( unsigned long int ) i ;
}

int main  ( ) {
    int k ;
    int n ;
    scanf ( "%d%d"  , & k , & n ) ;

  vec_int v2 ;
  vec_int_init ( & v2 ) ;
  mul_add ( k, 1 , & v2 ) ;
  for ( int i = 0 ; i < n ; ++ i )
    mul_add ( k, 0 , & v2 ) ;

  for ( int i = v2 . size - 1 ; i >= 0 ; -- i )
      printf ( "%u" , v2 . arr [ i ] ) ;
  puts ( "" ) ;
  vec_int_free ( & v2 ) ;
}

void mul_add ( int factor, int term, vec_int * const number ) {
    int carry = term;
    for ( int * digit = & ( number -> arr [ 0 ] ) ;
      digit < & ( number -> arr [ number -> size ] ) ;
      ++ digit ) {
        const int p = ( * digit ) * factor + carry;
        ( * digit ) = p % 10;
        carry = p / 10;
    }
    while (carry != 0) {
        vec_int_push_back ( number , carry % 10 ) ;
        carry /= 10;
    }
}

void vec_int_init ( vec_int * const v ) {
  v -> memsize = 4 ;
  v -> arr = malloc ( sizeof ( int ) * int_cast_ulong ( v -> memsize ) ) ;
  if ( ! ( v -> arr ) ) {
    v -> memsize = 0 ;
    v -> size = 0 ;
    return ;
  }
  v -> size = 1 ;
  v -> arr [ 0 ] = 0 ;
}

void vec_int_free ( vec_int * const v ) {
  free ( v -> arr ) ;
  v -> arr = 0 ;
  v -> memsize = 0 ;
  v -> size = 0 ;
}

void vec_int_push_back ( vec_int * const v , int const x ) {
  if ( v -> size >= v -> memsize ) {
    int const newmemsize = v -> memsize * 2 ;
    int * const p = realloc ( v -> arr ,
      sizeof ( int ) * int_cast_ulong ( newmemsize ) ) ;
    if ( ! p )
     return ;
    v -> arr = p ;
    v -> memsize = newmemsize ;
  }
  v -> arr [ v -> size ] = x ;
  ++ v -> size ;
}

$ echo 100 100 | ./степень 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

БЛОГ НА HUSL

Каков алгоритм вывода на экран больших чисел после возведения в степень?

Ответы (1 шт):