\documentclass[10pt,letterpaper]{article}
\usepackage{graphicx,amssymb}
\usepackage[colorlinks=true]{hyperref}

\topmargin -0.5in
\textheight 9in
\oddsidemargin=-0.05in
\evensidemargin=-0.05in
\textwidth 6.5in
\pagestyle{empty}

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand\ben{\begin{enumerate}}
\newcommand\een{\end{enumerate}}
\newcommand\vg{\vspace{2ex}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\ie}{{\it i.e.\ }}
\newcommand{\eg}{{\it e.g.\ }}
\newcommand{\eps}{\varepsilon}
\newcommand{\mbf}[1]{{\mathbf #1}}
\newcommand{\tbox}[1]{{\mbox{\tiny #1}}}


\begin{document}
\title{Math 56 Compu \& Expt Math, Spring 2013: Homework 7}
\date{\vspace{-2ex} due 10am Tuesday May 21st}
\maketitle

{\em
Last one! Extra time to let you work on Midterm 2 and projects.

In progress (I uploaded this version to let you start\ldots)
}

\ben

\item BBP algorithm for arbitrary binary digits of $\ln 2$.
\ben
\item Prove that $\ln 2 = \sum_{k=1}^\infty (1/k2^k)$.
[Hint: take $\frac{1}{1-x^{-1}} - 1 - \frac{1}{x}$, expand, and
integrate over $(a,+\infty)$, for some $a$, in two different ways.]

\item 
Write a Matlab (using standard doubles to represent integers),
or python (not arbitrary precision) function {\tt r = expmodk(b,n,k)}
that implements fast binary exponentiation (mod $k$) to compute
$r = b^n (\mbox{mod} k)$.
Include a driver that tests it on small numbers for which the answer
can be computed directly, including annoying cases like $n=0$, $k=1$, etc.

\item
Use this to code up the formula for $\{ 2^d \ln 2\}$ using the two sums.
You'll want Matlab's {\tt mod(x,1)} or python's {\tt x \% 1}
applied to {\em each} term in the 1st sum.
Include 50 or so terms in the exponentially convergent 2nd sum.
Output the fractional part in binary, e.g.\ using {\tt dec2bin} in Matlab.
[Hint: test your code by changing $d$ by e.g.\ 20 and checking
that the overlapping digits are the same.]

\item
Compute the 50 binary digits starting at the $10^7$th, for $\ln 2$,
and state how long your code took to run. [Hint: warm up on
smaller $d$ values, and make sure to check the last digits
using the above overlapping method.]
\een


\item
gcd

\item
quadratic sieve

\item
quadrature


\een
\end{document}

%log 2 digits via BBP ?  % few sec for 1e6; 77 sec for 1e7.
