// BigNumber example: Calculate decimal digits of Pi using Gosper's series
// http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

// #include <BigNumber.h>       // For a normal Arduino project
#include "BigNumber.h"          // For Wokwi simulation

// constants
const BigNumber one(1);
const BigNumber two(2);
const BigNumber three(3);
const BigNumber five(5);
const BigNumber ten(10);
const BigNumber twelve(12);
const BigNumber twentyseven(27);

// variables
BigNumber q(1);
BigNumber r(180);
BigNumber t(60);
BigNumber i(2);
BigNumber u, y;

void setup() {
  Serial1.begin(115200);
  BigNumber::begin(0);  // everything is integers throughout
}

void loop() {
  // Gibbons' spigot
  u = three * (three * i + one) * (three * i + two);
  y = (q * (twentyseven * i - twelve) + five * r) / (five * t);
  r = ten * u * (q * (five * i - two) + r - y * t);
  q = ten * q * i * (two * i - one);
  t *= u;
  Serial1.print(y);
  if (i++ == 2)
    Serial1.print('.');
}


Pi_decimal_spigot.ino

diagram.json

//
//  BigNumber.cpp
//  
//  Author:  Nick Gammon
//  Date:    22nd January 2013.
//  Contributors: Paul Stoffregen, S. Downey
//  Version: 3.5
//  Released into the public domain.
//  Added print function as suggested by Paul Stoffregen.
//  Changed printTo to return the length, as required.

#include "BigNumber.h"

int BigNumber::scale_ = 0;

// constructor
BigNumber::BigNumber () : num_ (NULL)
{
  bc_init_num (&num_);  // default to zero
} // end of constructor from string

// constructor
BigNumber::BigNumber (const char * s) : num_ (NULL)
{
  bc_str2num(&num_, s, scale_);
} // end of constructor from string

BigNumber::BigNumber (const int n) : num_ (NULL)  // constructor from int
{
  bc_int2num (&num_, n);
} // end of constructor from int

// copy constructor
BigNumber::BigNumber (const BigNumber & rhs)
  {
  if (this != &rhs)
    num_ = bc_copy_num (rhs.num_);
  }  // end of BigNumber::BigNumber
  
//operator=
BigNumber & BigNumber::operator= (const BigNumber & rhs)
{
  // gracefully handle self-assignment (eg. a = a;)
  if (this == &rhs )
    return *this;
  
  bc_free_num (&num_);  // get rid of old one
  num_ = bc_copy_num (rhs.num_);
  return *this;
} // end of BigNumber::BigNumber & operator=

// destructor - free memory used, if any
BigNumber::~BigNumber ()
{
  bc_free_num (&num_);
} // end of destructor

// set scale factor (number of places after the decimal point)
int BigNumber::setScale (const int scale)
{
  int old_scale = scale_;
  if (scale >= 0)
    scale_ = scale;
  else
    scale_ = 0;
  return old_scale;
}  // end of BigNumber::setScale

// initialize package
// supply scale (number of decimal places): default zero
void BigNumber::begin (const int scale)
{
  bc_init_numbers ();
  scale_ = scale;
} // end of BigNumber::begin

// finished with package
// free special numbers: zero, one, two
void BigNumber::finish ()
{
  bc_free_numbers ();
} // end of BigNumber::finish

// return a pointer to a string containing the number
// MUST FREE THIS after use!
// eg:  char * s = mynumber.toString ();
//      Serial.println (s);
//      free (s);
char * BigNumber::toString () const
{
  return bc_num2str(num_);
} // end of BigNumber::toString 

BigNumber::operator long () const
{
  return bc_num2long (num_);
} // end of BigNumber::operator long

// Allow Arduino's Serial.print() to print BigNumber objects!
size_t BigNumber::printTo(Print& p) const
{
  char *buf = bc_num2str(num_);
  size_t len = p.write(buf);
  free(buf);
  return len;
}

// add
BigNumber & BigNumber::operator+= (const BigNumber & n)
{ 
  bc_num result = NULL;
  bc_add (num_, n.num_, &result, scale_);
  bc_free_num (&num_);
  num_ = result;
  return *this; 
} // end of BigNumber::operator+= 

// subtract
BigNumber & BigNumber::operator-= (const BigNumber & n)
{ 
  bc_num result = NULL;
  bc_sub (num_, n.num_, &result, scale_);
  bc_free_num (&num_);
  num_ = result;
  return *this; 
}  // end of BigNumber::operator-=

// divide
BigNumber & BigNumber::operator/= (const BigNumber & n)
{ 
  bc_num result = NULL;
  bc_init_num (&result);  // in case zero
  bc_divide (num_, n.num_, &result, scale_);
  bc_free_num (&num_);
  num_ = result;
  return *this; 
} // end of BigNumber::operator/= 

// multiply
BigNumber & BigNumber::operator*= (const BigNumber & n)
{ 
  bc_num result = NULL;
  bc_multiply (num_, n.num_, &result, scale_);
  bc_free_num (&num_);
  num_ = result;
  return *this; 
}  // end of BigNumber::operator*=

// modulo
BigNumber & BigNumber::operator%= (const BigNumber & n)
{ 
  bc_num result = NULL;
  bc_init_num (&result);  // in case zero
  bc_modulo (num_, n.num_, &result, scale_);
  bc_free_num (&num_);
  num_ = result;
  return *this; 
}  // end of BigNumber::operator%=


// ----------------------------- COMPARISONS ------------------------------

// compare less with another BigNumber
bool BigNumber::operator< (const BigNumber & rhs) const
{
  return bc_compare (num_, rhs.num_) < 0;
} // end of BigNumber::operator<


// compare greater with another BigNumber
bool BigNumber::operator> (const BigNumber & rhs) const
{
  return bc_compare (num_, rhs.num_) > 0;
} // end of BigNumber::operator>

// compare less-or-equal with another BigNumber
bool BigNumber::operator<= (const BigNumber & rhs) const
{
  return bc_compare (num_, rhs.num_) <= 0;
} // end of BigNumber::operator<=

// compare greater-or-equal with another BigNumber
bool BigNumber::operator>= (const BigNumber & rhs) const
{
  return bc_compare (num_, rhs.num_) >= 0;
} // end of BigNumber::operator>=

// compare not equal with another BigNumber
bool BigNumber::operator!= (const BigNumber & rhs) const
{
  return bc_compare (num_, rhs.num_) != 0;
} // end of BigNumber::operator!=

// compare equal with another BigNumber
bool BigNumber::operator== (const BigNumber & rhs) const
{
  return bc_compare (num_, rhs.num_) == 0;
} // end of BigNumber::operator==

// special comparisons
bool BigNumber::isNegative () const
{
  return bc_is_neg (num_) == true;
} // end of BigNumber::isNegative

bool BigNumber::isZero () const
{
  return bc_is_zero (num_) == true;
} // end of BigNumber::isZero

bool BigNumber::isNearZero () const
{
  return bc_is_near_zero (num_, scale_) == true;
} // end of BigNumber::isNearZero

// ----------------------------- OTHER OPERATIONS ------------------------------

// square root
BigNumber BigNumber::sqrt () const
{
  BigNumber result (*this);
  bc_sqrt (&result.num_, scale_);
  return result;
} // end of BigNumber::sqrt

// raise to power
BigNumber BigNumber::pow (const BigNumber power) const
{
  BigNumber result;
  bc_raise (num_, power.num_, &result.num_, scale_);
  return result;
} // end of BigNumber::pow

void BigNumber::divMod (const BigNumber divisor, BigNumber & quotient, BigNumber & remainder) const
{
  bc_divmod (num_, divisor.num_, &quotient.num_, &remainder.num_, scale_);
}

// raise number by power, modulus modulus
BigNumber BigNumber::powMod (const BigNumber power, const BigNumber & modulus) const
{
  BigNumber result;
  bc_raisemod (num_, power.num_, modulus.num_, &result.num_, scale_);
  return result;
}


BigNumber.cpp

//
//  BigNumber.h
//
//  Author:  Nick Gammon
//  Date:    22nd January 2013.
//  Contributors: Paul Stoffregen, S. Downey
//  Version: 3.5
//  Released into the public domain.
//  Added print function as suggested by Paul Stoffregen.

#ifndef _BigNumber_h
#define _BigNumber_h

#include <stddef.h>
#include <Arduino.h>

extern "C" 
{
 #include "number.h" 
}

class BigNumber : public Printable
{
  
  // the current scaling amount - shared amongst all BigNumbers
  static int scale_;

  // member variable (the big number)
  bc_num        num_;

public:
 
  // constructors
  BigNumber ();  // default constructor
  BigNumber (const char * s);   // constructor from string
  BigNumber (const int n);  // constructor from int
  // copy constructor
  BigNumber (const BigNumber & rhs); 
 
  // destructor  
  ~BigNumber ();
  
  // static methods: initialize package, and set global scaling factor
  static void begin (const int scale = 0);
  static void finish ();  // free memory used by 'begin' method
  static int setScale (const int scale = 0);
  
  // for outputting purposes ...
  char * toString () const;  // returns number as string, MUST FREE IT after use!
  operator long () const;
  virtual size_t printTo(Print& p) const; // for Arduino Serial.print()

  // operators ... assignment
  BigNumber & operator= (const BigNumber & rhs);
  
  // operations on the number which change it (eg. a += 5; )
  BigNumber & operator+= (const BigNumber & n);
  BigNumber & operator-= (const BigNumber & n);
  BigNumber & operator/= (const BigNumber & n);
  BigNumber & operator*= (const BigNumber & n);
  BigNumber & operator%= (const BigNumber & n);  // modulo

  // operations on the number which do not change it (eg. a = b + 5; )
  BigNumber operator+ (const BigNumber & n) const { BigNumber temp = *this; temp += n; return temp; };
  BigNumber operator- (const BigNumber & n) const { BigNumber temp = *this; temp -= n; return temp; };
  BigNumber operator/ (const BigNumber & n) const { BigNumber temp = *this; temp /= n; return temp; };
  BigNumber operator* (const BigNumber & n) const { BigNumber temp = *this; temp *= n; return temp; };
  BigNumber operator% (const BigNumber & n) const { BigNumber temp = *this; temp %= n; return temp; };
  
  // prefix operations
  BigNumber & operator++ () { *this += 1; return *this; }
  BigNumber & operator-- () { *this -= 1; return *this; }
  
  // postfix operations (cannot return by reference)
  // we make a temporary object, change our current object, return the temporary one
  // if we returned a reference it would cease to exist, so we have to return a copy
  BigNumber operator++ (int) { BigNumber temp = *this; *this += 1; return temp; }
  BigNumber operator-- (int) { BigNumber temp = *this; *this -= 1; return temp; }
  
  // comparisons
  bool operator<  (const BigNumber & rhs) const;
  bool operator<  (const int rhs) const { return *this < BigNumber (rhs); }
  bool operator>  (const BigNumber & rhs) const;
  bool operator>  (const int rhs) const { return *this > BigNumber (rhs); }
  bool operator<= (const BigNumber & rhs) const;
  bool operator<= (const int rhs) const { return *this <= BigNumber (rhs); }
  bool operator>= (const BigNumber & rhs) const;
  bool operator>= (const int rhs) const { return *this >= BigNumber (rhs); }
  bool operator!= (const BigNumber & rhs) const;
  bool operator!= (const int rhs) const { return *this != BigNumber (rhs); }
  bool operator== (const BigNumber & rhs) const;
  bool operator== (const int rhs) const { return *this == BigNumber (rhs); }

  // quick sign test
  bool isNegative () const;
  // quick zero test
  bool isZero () const;
  
  // In some places we need to check if the number is almost zero.
  // Specifically, all but the last digit is 0 and the last digit is 1.
  // Last digit is defined by scale.
  bool isNearZero () const;
  
  // other mathematical operations
  BigNumber sqrt () const;
  BigNumber pow (const BigNumber power) const;
  // divide number by divisor, give quotient and remainder
  void divMod (const BigNumber divisor, BigNumber & quotient, BigNumber & remainder) const;
  // raise number by power, modulus modulus
  BigNumber powMod (const BigNumber power, const BigNumber & modulus) const;
  
};  // end class declaration


#endif


BigNumber.h

/*
* config.h
* number.c from GNU bc-1.06 exports some symbols without the bc_ prefix.
* This header file fixes this without touching either number.c or number.h
* (luckily, number.c already wants to include a config.h).
* Clients of number.c should include config.h before number.h.
*/

#include <string.h>
#include <limits.h>
#define NDEBUG 1

#define _zero_		bc_zero
#define _one_		bc_one
#define _two_		bc_two
#define num2str		bc_num2str
#define mul_base_digits bc_mul_base_digits

#define bc_rt_warn		bc_error
#define bc_rt_error		bc_error
#define bc_out_of_memory()	bc_error(0)

void bc_error(const int mesg);



bcconfig.h

number.c

/* number.h: Arbitrary precision numbers header file. */
/*
    Copyright (C) 1991, 1992, 1993, 1994, 1997, 2000 Free Software Foundation, Inc.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License , or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING.  If not, write to:

      The Free Software Foundation, Inc.
      59 Temple Place, Suite 330
      Boston, MA 02111-1307 USA.


    You may contact the author by:
       e-mail:  philnelson@acm.org
      us-mail:  Philip A. Nelson
                Computer Science Department, 9062
                Western Washington University
                Bellingham, WA 98226-9062
       
*************************************************************************/

#ifndef _NUMBER_H_
#define _NUMBER_H_
  
// errors, warnings

#define BC_ERROR_OUT_OF_MEMORY 0
#define BC_ERROR_EXPONENT_TOO_LARGE_IN_RAISE 1
#define BC_WARNING_NON_ZERO_SCALE_IN_EXPONENT -1
#define BC_WARNING_NON_ZERO_SCALE_IN_BASE -2
#define BC_WARNING_NON_ZERO_SCALE_IN_MODULUS -3


typedef enum {PLUS, MINUS} sign;

typedef struct bc_struct *bc_num;

typedef struct bc_struct
    {
      sign  n_sign;
      int   n_len;	/* The number of digits before the decimal point. */
      int   n_scale;	/* The number of digits after the decimal point. */
      int   n_refs;     /* The number of pointers to this number. */
      bc_num n_next;	/* Linked list for available list. */
      char *n_ptr;	/* The pointer to the actual storage.
			   If NULL, n_value points to the inside of
			   another number (bc_multiply...) and should
			   not be "freed." */
      char *n_value;	/* The number. Not zero char terminated.
			   May not point to the same place as n_ptr as
			   in the case of leading zeros generated. */
    } bc_struct;


/* The base used in storing the numbers in n_value above.
   Currently this MUST be 10. */

#define BASE 10

/*  Some useful macros and constants. */

#define CH_VAL(c)     (c - '0')
#define BCD_CHAR(d)   (d + '0')

#ifdef MIN
#undef MIN
#undef MAX
#endif
#define MAX(a,b)      ((a)>(b)?(a):(b))
#define MIN(a,b)      ((a)>(b)?(b):(a))
#define ODD(a)        ((a)&1)

#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

#ifndef LONG_MAX
#define LONG_MAX 0x7ffffff
#endif


/* Global numbers. */
extern bc_num _zero_;
extern bc_num _one_;
extern bc_num _two_;


/* Function Prototypes */

/* Define the _PROTOTYPE macro if it is needed. */

#ifndef _PROTOTYPE
#define _PROTOTYPE(func, args) func args
#endif

_PROTOTYPE(void bc_init_numbers, (void));

_PROTOTYPE(void bc_free_numbers, (void));

_PROTOTYPE(bc_num bc_new_num, (int length, int scale));

_PROTOTYPE(void bc_free_num, (bc_num *num));

_PROTOTYPE(bc_num bc_copy_num, (bc_num num));

_PROTOTYPE(void bc_init_num, (bc_num *num));

_PROTOTYPE(void bc_str2num, (bc_num *num, const char *str, int scale));

_PROTOTYPE(char *bc_num2str, (bc_num num));

_PROTOTYPE(void bc_int2num, (bc_num *num, int val));

_PROTOTYPE(long bc_num2long, (bc_num num));

_PROTOTYPE(int bc_compare, (bc_num n1, bc_num n2));

_PROTOTYPE(char bc_is_zero, (bc_num num));

_PROTOTYPE(char bc_is_near_zero, (bc_num num, int scale));

_PROTOTYPE(char bc_is_neg, (bc_num num));

_PROTOTYPE(void bc_add, (bc_num n1, bc_num n2, bc_num *result, int scale_min));

_PROTOTYPE(void bc_sub, (bc_num n1, bc_num n2, bc_num *result, int scale_min));

_PROTOTYPE(void bc_multiply, (bc_num n1, bc_num n2, bc_num *prod, int scale));

_PROTOTYPE(int bc_divide, (bc_num n1, bc_num n2, bc_num *quot, int scale));

_PROTOTYPE(int bc_modulo, (bc_num num1, bc_num num2, bc_num *result,
			   int scale));

_PROTOTYPE(int bc_divmod, (bc_num num1, bc_num num2, bc_num *quot,
			   bc_num *rem, int scale));

_PROTOTYPE(int bc_raisemod, (bc_num base, bc_num expo, bc_num mod,
			     bc_num *result, int scale));

_PROTOTYPE(void bc_raise, (bc_num num1, bc_num num2, bc_num *result,
			   int scale));

_PROTOTYPE(int bc_sqrt, (bc_num *num, int scale));

_PROTOTYPE(void bc_out_num, (bc_num num, int o_base, void (* out_char)(int),
			     int leading_zero));

#endif

