Built-in, unlimited precision, big integer arithmetik

Notices and updates
Locked
Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

The next version of newLISP features built-in, unlimited precision, big integer arithmetik. As I am currently travelling, I cannot make a full development release until the second week of May. Anybody interested can find binaries for OSX and Windows here:

http://www.newlisp.org/downloads/develo ... nprogress/

Linux users would have to compile from the source package.

Details on how to use this new feature can be found here:

http://www.newlisp.org/downloads/develo ... ml#big_int

HPW
Posts: 1390
Joined: Thu Sep 26, 2002 9:15 am
Location: Germany
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by HPW »

Hello Lutz,

Great new option.
Anybody interested can find binaries for OSX and Windows here:
Any chance to post also a DLL binary?

Regards
Hans-Peter

johu
Posts: 143
Joined: Mon Feb 08, 2010 8:47 am

Re: Built-in, unlimited precision, big integer arithmetik

Post by johu »

Hello, Lutz.

It's fine!

I have just stated The Euler Project in newLISP.

And I translated newLISP-manual to Japanese.
Then, I have some opinions.

line 1652-1653
Integers are 64-bit numbers including the sign bit 8.9.7). Valid integers
are numbers between -9,223,372,036,854,775,808 and
    ↓
Integers are 64-bit numbers (including the sign bit, 32-bit before version 8.9.7).
Valid integers are numbers between -9,223,372,036,854,775,808 and
maybe.

line 5629-5632
<tr>
<td><a href="#bigint">bigint</a></td>
<td>convert a number to big integer format</td>
</tr>
bitint is string operator? My mistake, sorry.(2013/4/14 added)

line 16607-16609
<p>See also <a href="#letn">letn</a> for an incremental or nested form of
<tt>let</tt> and local for initializing to <tt>nil</tt>. See <a href="#local">local</a>
for automatic initialization of variables to <tt>nil</tt>.</p>
I have heared that local is deprecated and have been taken out of the documentation.
But, there is in this manual.
Which is right?
I am glad to see local there.

Thanks,
Last edited by johu on Sun Apr 14, 2013 7:17 am, edited 1 time in total.

HPW
Posts: 1390
Joined: Thu Sep 26, 2002 9:15 am
Location: Germany
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by HPW »

Thanks for the DLL!
Hans-Peter

lotabout
Posts: 8
Joined: Sat Mar 09, 2013 9:13 am

Re: Built-in, unlimited precision, big integer arithmetik

Post by lotabout »

Thanks Lutz.

It's very nice to feel that the tool in hand becomes much more powerful.

Works all right under Linux for now.

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by cormullion »

Nice addition, Lutz. Out of interest, why did you decide to add big number support now?

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

My interest in big numbers came to life when doing the Euler project examples. Over the years people also have asked for big integer support again and again and working with the GMP GNU gmp.lsp module was a bit clumsy, because all numbers have to be delievered to the GMP library as strings and special operators be used. Having large integer support built into the language is much nicer.

Thanks to everybody for comments and manual corrections. The bigint function now also converts from strings, like its smaller sibling int. The binaries will be updated later, when I have acccess to OSX.

There is an interesting site at google about large numbers by Sbiis Saibian here:
https://sites.google.com/site/largenumbers/home

the following words from the introduction:

While the venues large numbers can open up in your mind can be quite rewarding, be warned that it must by necessity end in human futility. For we can no more imagine the end of numbers than we could wait out eternity. An earnest study of large numbers will completely shift the way you think about infinity, and your mind shall be forever changed for it.

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by cormullion »

Interesting. I'm going to play with it soon... And there's some editing work required in various other places, too, which I might get round to some time.

(arithmetiC, by the way, not arithmetiK), although it look good with a K...

xytroxon
Posts: 296
Joined: Tue Nov 06, 2007 3:59 pm
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by xytroxon »

cormullion wrote:(arithmetiC, by the way, not arithmetiK), although it look good with a K...
Bist du wahnsinnig?
http://de.wikipedia.org/wiki/Arithmetik

-- xytroxon ;o)
"Many computers can print only capital letters, so we shall not use lowercase letters."
-- Let's Talk Lisp (c) 1976

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by cormullion »

xytroxon wrote:Bist du wahnsinnig?
Ja veilleicht, ein bißchen, aber für programmieren mit NeueLisp wir mussen alles Englisch sprachen.

(Sorry, Lutz, my German lessons are a distant memory...)

xytroxon
Posts: 296
Joined: Tue Nov 06, 2007 3:59 pm
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by xytroxon »

Ditto...

Since the death of my 4 German speaking great grandparents nearly 50 years ago, sadly, our family retains very few German words in their daily vocabulary.

Lutz's amazing command of the American er. "English" language is almost flawless.

Almost ;o)

-- xytroxon
"Many computers can print only capital letters, so we shall not use lowercase letters."
-- Let's Talk Lisp (c) 1976

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

almost flawless
"almost", that is why I always appreciate help on manual changes and additions :-)

Updated binaries with speedups on / and % and bigint working on strings too, are here:
http://www.newlisp.org/downloads/develo ... nprogress/

The OSX executable is made on 10.8 Intel Mountain Lion - cannot make PPC executables at the moment.

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

update of binary executables including osx ppc here:

http://www.newlisp.org/downloads/develo ... nprogress/

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Built-in, unlimited precision, big integer arithmetik

Post by rickyboy »

(λx. x x) (λx. x x)

kosh
Posts: 72
Joined: Sun Sep 13, 2009 5:38 am
Location: Japan
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by kosh »

hi.

Does bigint function allow non-numerical characters?

Code: Select all

newLISP v.10.5.0 32-bit on Win32 IPv4/6 UTF-8 libffi, options: newlisp -h

> (bigint "HELLO")
264111L
> (bigint "")
(null)L
> (bigint "-L")
; segmentation fault
and, what value returns with a floating-point string?

Code: Select all

> (int "3.14")
3
> (bigint "3.14")
2814L  ; expect 3L

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

At the moment bigint only allows wellformed integers when the argument is a string. Floats must be passed as floats not in a string.

Code: Select all

> (bigint 3.14)
3L
> (bigint 123e20)
12300000000000000000000L
> (bigint 1234567)
1234567L
> (bigint "1234567890")
1234567890L
> (bigint "1234567890123456789012345")
1234567890123456789012345L
> 
thanks Kosh for reporting this.

see also here: http://www.newlisp.org/downloads/develo ... nprogress/

kosh
Posts: 72
Joined: Sun Sep 13, 2009 5:38 am
Location: Japan
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by kosh »

Thanks, Lutz.

I found another problem.
division operator (/) with bigint works strangely.

Code: Select all

> (/ 123000000000L 1)
123L
> (/ 12300000000000000000000000000L 1)
12300000000000000001L
> (/ 123000000000000000000000000000L 1)
123000000001^[,),(-*,(L
regards.

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

Thanks Kosh.

I wish that would have been detected during the three weeks of the development version 10.4.8.

I have a qa-specific-tests/qa-bigint and qa-specific-tests/qa-factorfibo running millions of operations but not testing for trailing/embedded 0 bigint digits in division.

ps: please keep on testing

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Built-in, unlimited precision, big integer arithmetik

Post by Lutz »

all fixed now here: http://www.newlisp.org/downloads/develo ... nprogress/

I will do a development release on Monday/Tuesday. Although 10.5.1 will be identical to 10.5.0 except for big integer division fixes, I want to wait a little before doing a Maintenance Release 10.5.2. Just want to be sure nothing else pops up in the big integer area.

The whole thing was pretty intense to develop it. Most of the code, you see on the net, doesn't have good performance, and it took the whole April and part of May to get speed, trying out various approaches. The division algorithm is the old grade school algorithm, but tweaked for base 1000,000,000 and using float arithmetik on bigint digits. Others have done this before, but I couldn't find anything appropriate ready-made.

The code designed in 10.5.0 didn't handle certain edge cases, which arise when doing mixed float and integer arithmetik. That is why Kosh discovered problems with trailing zeros. Turns out that embedded and base 10^9 aligned zeros didn't work as well and trailing zero's in results where also suppressed.

I hope everything is fine now. Whoever understands something about big integer arithmetic, please test!

My own test routines are in newlisp-10.5.1/qa-specific-tests/qa-bigint

Locked