yasarcereen
diff --git a/‎bundles/03-math-1/03_math1.pdf‎
492 Bytes b/‎bundles/03-math-1/03_math1.pdf‎
492 Bytes
diff --git a/‎bundles/03-math-1/latex/03_math1.tex‎
Lines changed: 10 additions & 2 deletions b/‎bundles/03-math-1/latex/03_math1.tex‎
Lines changed: 10 additions & 2 deletions
@@ -1348,6 +1348,7 @@ \subsection{Fast Exponentiation Approach }
 #define mod 1000000007
 
 long long fastExp(long long n, long long k){
+    n %= mod;
     if(k == 0) return 1;
     if(k == 1) return n;
 
@@ -1356,6 +1357,13 @@ \subsection{Fast Exponentiation Approach }
     // If k is odd return n * temp * temp
     // If k is even return temp * temp
     // Take mod, since we can have a large number that overflows from long long
+    
+    // The product of two factors that are each bounded by mod is bounded by
+    // mod squared. If we multiply this product with yet another factor that
+    // is bounded by mod, the result will be bounded by mod cubed. As mod is
+    // equal to 1000000007 by default, the result might not fit into
+    // long longs, leading to an overflow. To avoid that, we must take
+    // the modulus of n * temp before multiplying it with temp yet again.
     if((k&1) == 1) return ((n * temp) % mod * temp) % mod;
     return (temp * temp) % mod;
 }
@@ -1366,7 +1374,7 @@ \subsection{Fast Exponentiation Approach }
     // Calculate the runtime of the function.
     clock_t tStart = clock();
 
-    long long res = expon(n, k);
+    long long res = fastExp(n, k);
     printf("Time taken: %.6fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
     printf("%lld\n", res);
 
@@ -1668,4 +1676,4 @@ \subsection{Meet in the Middle }
 
 \end{thebibliography}
 
-\end{document}
+\end{document}