2.8: Discussion

Last updated
Save as PDF

Page ID: 97859

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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\), 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.”

“Thanks for your kind remarks,” replied Bob, with the rest of the group noting that that Alice was being pretty harsh on Bob and not for any good reason.

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.”

Dave said “What about factoring? Can your netbook with its fancy software for strings factor big integers?” Xing said that he would try some sample problems and report back. Carlos said “Factoring an integer with several hundred digits is likely to be very challenging, not only for a netbook, but also for a super computer. For example, suppose the given integer was either a prime or the product of two large primes. Detecting which of these two statements holds could be very difficult.”

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?”

Zori was not happy. She gloomily envisioned a future job hunt in which she was compelled to use big integer arithmetic as a job skill. Arrgghh.