 Over coffee, Xing said that he had been experimenting with the SageMath software discussed in Chapter 1. He understood that SageMath was treating a big integer as a string. Xing enthusiastically reported that he had asked SageMath to find the sum $$a+b$$ of two large integers $$a$$ and $$b\text{,}$$ each having more than $$800$$ digits. The software found the answer about as fast as he could hit the enter key on his netbook. “That’s not so impressive,” Alice interjected. “A human, even Bob, could do this in a couple of minutes using pencil and paper.”
Dave took up Bob’s case by remarking, “Very few humans, not even you Alice, would want to tackle finding the product of $$a$$ and $$b$$ by hand.” Xing jumped back in with, “That’s the point. Even a tiny netbook can find the product very, very quickly. In fact, I tried it out with two integers, each having more than one thousand digits. It found the product in about one second.” Ever the skeptic, Zori said, “You mean you carefully typed in two integers of that size?” Xing quickly replied “Of course not. I just copied and pasted the data from one source to another.” Yolanda said, “What a neat trick that is. Really cuts down the chance of an error.”
Undeterred, Dave continued, “What about exponentiation? Can your software calculate $$a^b$$ when $$a$$ and $$b$$ are large integers?” Xing said “That shouldn’t be a problem. After all, $$a^b$$ is just multiplying $$a$$ times itself a total of $$b$$ times, and if you can do multiplication quickly, that’s just a loop.” Yolanda said that the way Xing was describing things, he was actually talking about a program with nested loops so it might take a long time for such a program to halt. Carlos was quiet but he thought there might be ways to speed up such computations.
By this time, Alice reinserted herself into the conversation: “Hey guys. While you were talking, I was looking for big integer topics on the web and found this problem. ‘Is $$838200020310007224300$$ a Catalan number?’ How would you answer this? Do you have to use special software?”