/*
*************************************************************************
* Compute the N-th power of 3 and print the result
*
* Yes, it is that simple: compute 3^N and print out the result as
* *fast* as possible. N is a non-negative integer number not
* exceeding 2000. Yes, it can be that big, that's the catch you've
* been looking for. Modern cryptography often requires raising
* numbers to very big powers, so here's a little exercise.
*
* The program should read the number N from the file "pow3.in"
* and print 3^N. You should write no more than 70 digits per line.
* If the result appears longer than that, put a backslash after
* the 70-th digit, and continue printing digits on the next line.
* Don't print leading zeros!
*
* For example, if the file "pow3.in" contains "100", the program
* should print
* 3^100
* 515377520732011331036461129765621272702107522001
*
* If the file "pow3.in" contains "1000", the program
* should print
* 3^1000
* 1322070819480806636890455259752144365965422032752148167664920368226828\
* 5973467048995407783138506080619639097776968725823559509545821006189118\
* 6534272525795367402762022519832080387801477422896484127439040011758861\
* 8041128947815623094438061566173054086674490506178125480344405547054397\
* 0388958174653682549161362208302685637785822902284163983078878969185564\
* 0408489893760937324217184635993869551676501894058810906042608967143886\
* 4102814350385648747165832010614366132173102768902855220001
*
* Performance counts!
* The program has to handle numbers as big as 2000. If your program takes
* more than 4 secs to raise 3 to the power of order 2000, it's considered
* failed the test. Moreover, you would be punished by 20 minutes, or by the
* time it takes a judge to reboot his PC and restore his working
* environment, whichever is bigger (keep in mind that the judge would
* probably be very mad at you...) So, be careful in testing your program
* before submission.
*
* The algorithm
* The longest operation appears not a multiplication of a very long integer
* by 3, but its division by 10 to figure out the next decimal digit to
* print. To cut down this expense, we perform arithmetic in decimal rather
* than in binary. Furthermore, we make radix 10000. It means, that a single
* "digit" (ranging from 0 to 9999) can comfortably fit into a short
* int, and even have space for a carry (which can be 0, 1, 2 or 3).
* Since the log10(3) = 0.477 is almost 0.5, 3^2000 < 10^1000, so we need
* at most 1000/4 = 250 radix-10000 digits.
* Note, multiplication by three is most conveniently done as a shift
* followed by addition. So, the present program uses no multiplication
* or division to compute and print 3^N, isn't that neat?
*
* $Id: pow3.c,v 1.2 2002/10/28 21:03:54 oleg Exp oleg $
*
*************************************************************************
*/
#include
#include
#include
typedef short int DIGIT; /* Radix-10000 digit with a room for carry */
#define MAX_DIGITS 251 /* Max no. of digits we expect in a result*/
static DIGIT Digits[MAX_DIGITS];/* Our result in REVERSE order of digits */
/* That is, Digits[0] is the least */
/* significant digit */
static int valid_digits; /* How many digits in Digits are valid */
/* Prepare the stuff for work */
static void init_digits(void)
{
memset(Digits,0,sizeof(Digits));
valid_digits = 0;
}
/* Compute 3^N in Radix-10000 digits */
static void raise_3(const long N)
{
register int i;
register DIGIT * dp;
register int carry = 0;
assert( N >= 0 );
Digits[valid_digits++] = 1;
if( N == 0 )
return; /* 3^0 is 1 always */
for(i=1; i<=N; i++) /* Computing 3^i */
{
carry = 0;
for(dp=Digits; dp= 30000 ) /* Can happen if dp[0] was */
new_digit -= 30000, carry = 3; /* 9999 and was a carry in */
else if( new_digit >= 20000 )
new_digit -= 20000, carry = 2;
else if( new_digit >= 10000 )
new_digit -= 10000, carry = 1;
else
carry = 0;
*dp = new_digit;
}
if( carry )
Digits[valid_digits++] = carry;
}
assert( valid_digits < MAX_DIGITS );
}
/* Print the digits (in reverse order!)*/
static void print_digits(void)
{
const int digits_per_line = 70;
register int counter = 0;
register DIGIT * dp;
char buffer[10];
if( valid_digits == 0 || (valid_digits == 1 && Digits[0] == 0) )
{
printf("0\n");
return;
}
assert( Digits[valid_digits-1] > 0 );
/* We don't want to print leading 0 */
{ /* handle the most-signif digit w/ care*/
sprintf(buffer,"%d",Digits[valid_digits-1]);
printf("%s",buffer);
counter = strlen(buffer);
assert( counter <= 4 );
}
/* print less-significant digits */
/* with *all* zeros */
for(dp=&Digits[valid_digits-1]-1; dp >= Digits; dp--)
{
register char * p;
sprintf(buffer,"%04d",*dp);
for(p=buffer; *p != '\0'; p++,counter++)
{
if( counter >= digits_per_line )
printf("\\\n"), counter = 0;
putchar(*p);
}
}
putchar('\n');
}
int main(void)
{
const char * input_file_name = "pow3.in";
FILE * fp;
long int N;
if( (fp=fopen(input_file_name,"r")) == (FILE *)0 )
perror("Failed to open the input file"),
exit(4);
if( fscanf(fp,"%ld",&N) != 1 )
fprintf(stderr,"Failed to read the number N"),
exit(4);
fclose(fp);
init_digits();
printf("\n3^%ld\n",N);
assert( N <= (MAX_DIGITS-1)*4*2 );
raise_3(N);
print_digits();
return 0;
}