Code covered by the BSD License  

Highlights from
sumsqint

5.0

5.0 | 1 rating Rate this file 10 Downloads (last 30 days) File Size: 4.32 KB File ID: #24798

sumsqint

by

 

20 Jul 2009 (Updated )

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.

| Watch this File

File Information
Description

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.

Acknowledgements

Variable Precision Integer Arithmetic inspired this file.

MATLAB release MATLAB 7.8 (R2009a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (1)
22 Jul 2009 John D'Errico

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
17 Aug 2009

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.

Contact us