File Exchange

image thumbnail

sumsqint

version 1.1 (4.32 KB) by

Finds all distinct ways of writing a number as the sum of squares, i.e. solve x^2+y^2=n for 0<=x<=y.

1 Download

Updated

View License

Example:

   sumsqint(1) % returns [0,1]
   sumsqint(65) % returns [1,8;4,7]

sumsqint can work with large numbers if they are factored, e.g. solve x^2+y^2=(25e6)^2:
   sumsqint(repmat(factor(25e6),1,2)) % returns 9x2 array

sumsqint works with variable precision integers if you have John D'Errico's Variable Precision Integer toolbox (20 July 2009 update) - see links below.

   sumsqint(vpi(5)^100) % returns 51x2 vpi array
   sumsqint(vpi(65)^100) % returns 5101x2 vpi array

The algorithm uses Gaussian integer factorization. See the help for more details.

Comments and Ratings (1)

John D'Errico

John D'Errico (view profile)

A nifty piece of code. Well written. Good help. Fast - even on my old cpu.

tic,xy = sumsqint(vpi(51)^32);toc
Elapsed time is 3.341508 seconds.

xy
xy =
                    0 2094704750199298376445300801
     30716516552930718230081601 2094479526306800294009550720
    180465099249163605704475624 2086916466574667319894682335
    211048005566589191194875615 2084045760019167609213236376
    389810107080067581524800449 2058114688477231401347749200
    419948158440662717915958480 2052177266887488219864204351
    595187985793527352363191624 2008367310049272061252396065
    624574464800990440465293345 1999423599047000686612625976
    794508588038500176810750399 1938180614401189862809267680
    822844426109404969034724960 1926321634859606979062120001
    985743411858493353621318024 1848268897234675038039971295
   1012740232867550772089860575 1833615338951679921429565176
   1141312248313811332042623120 1756472129683923585457907649
   1166946244920716396566413249 1739547197397341212272914160
   1312474653765815584332588255 1632543498265760609883402024
   1336272971277049795744294824 1613121984458060091449141025
   1470279898076299222086296640 1492000339081815417640023999

Updates

1.1

added support for factored inputs; fixed a bug in the handling of vpi numbers with prime factors larger than 100; added option to remember newly found gaussian prime factors.

MATLAB Release
MATLAB 7.8 (R2009a)
Acknowledgements

Inspired by: Variable Precision Integer Arithmetic

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video