Home
JAQForum Ver 24.01
Log In or Join  
Active Topics
Local Time 10:38 25 Nov 2024 Privacy Policy
Jump to

Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me.

Forum Index : Microcontroller and PC projects : Big Integers in MM Basic

Author Message
TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6098
Posted: 11:18pm 06 Feb 2012
Copy link to clipboard 
Print this post

MM Basic CAN do big integer maths!

The included code uses integer maths to calculate 1, 1×2, 1×2×3, 1×2×3×4, etc. the successive factorial numbers.
The limit in MM Basic is the length of a string or 255 digits.
At this stage, only positive integers are allowed as inputs.
This code is SLOW and I have not made any attempt to speed it up. Working in base 1000 (3 digits at a time) is the obvious way to gain speed but this exercise was a proof of concept rather than good code.
I know a lot more about MM Basic subroutine now!
It needs MM Basic V3.1 as it uses user defined subroutines. Converting to gosubs and line numbers is a task for someone else.

Now I need to go the next step and allow negative numbers as inputs.

' integer maths by TassyJim 07 Feb 2012
a$ = "13"
For i = 0 To 15 ' demo of the four operations
add( a$ , Str$( i ),res$ )
Print a$;" + ";i;" = ";res$
min( a$ , Str$( i ),res$ )
Print a$;" - ";i;" = ";res$
multy( a$ , Str$( i ),res$ )
Print a$;" * ";i;" = ";res$
div( a$ , Str$( i ),res$ )
Print a$;" / ";i;" = ";res$
Print
Next i

a$="1"
For i = 1 To 55 ' printing up to factorial 55.
b$=Str$(i)
multy(a$, b$, res$)
Print b$;"! = ";res$;" (";len(res$);" )"
a$=res$
Next i

End

Sub div( a$ , b$, c$ ) ' given a$ and b$, returns a/b in c$
Local f, i, d, t, try$, nr$, a1$, b1$, a2$, z$
a1$=a$ : b1$=b$ : c$="" ' make copies of a$ and b$ to preserve originals
If Val( b$ ) = 0 Then ' divide by zero
c$ = "error"
Else
For i = Len( a1$ ) - Len( b1$ ) To 0 Step -1
f = 0
nr$ = "0"
z$=String$(i,"0")
For d = 0 To 9
md( b1$ + z$ , d, try$ )
big( a1$ , try$, t )
If t Then
f = d
nr$ = try$
EndIf
Next d
c$ = c$ + Str$( f )
If f > 0 Then
min( a1$ , nr$, a2$ )
a1$ = a2$
EndIf
Next i
EndIf
trim (c$)
End Sub

Sub multy( a$ , b$, c$ ) ' given a$ and b$, returns the sum in c$
Local i, h$, a1$, b1$, t$, d$, z$
a1$=a$ : b1$=b$ : c$="" ' make copies of a$ and b$ to preserve originals
If Len( b1$ ) > Len( a1$ ) Then ' swap number for greater speed
h$ = a1$
a1$ = b1$
b1$ = h$
EndIf
For i = Len( a1$ ) To 1 Step -1
z$=String$(Len( a1$ )-i,"0")
md( b1$ , Val( Mid$( a1$ , i , 1 ) ) , t$)
add( c$ , t$+ z$ ,d$)
c$=d$
Next i
trim (c$)
End Sub

Sub md( a$ , nr, c$ ) ' multiply a$ by a single digit, result in c$
Local hold, carry, i
carry = 0 : c$=""
For i = Len( a$ ) To 1 Step -1
hold = Val( Mid$( a$ , i , 1 ) ) * nr + carry
carry = Int( hold / 10 )
c$ = Str$( hold Mod 10 ) + c$
Next i
If carry > 0 Then c$ = Str$( carry ) + c$
End Sub

Sub samelen (a$, b$) ' pads the shorter variable with leading zeros
dif=Abs(Len( a$ )-Len( b$ ))
If dif>0 Then
z$=String$(dif,"0")
If Len( a$ ) < Len( b$ ) Then
a$ = z$+a$
Else
b$ = z$+b$
EndIf
EndIf
End Sub

Sub add( a$ , b$, c$ ) ' given a$ and b$, returns the sum in c$
Local carry, hold, i,a1$, b1$
c$="" : a1$=a$ : b1$=b$
samelen a1$ , b1$
For i = Len( a1$ ) To 1 Step -1
hold = Val( Mid$( a1$ , i , 1 ) ) + Val( Mid$( b1$ , i , 1 ) ) + carry
carry = Int( hold / 10 )
x$=Str$( hold Mod 10 )
c$ = Right$( x$,1) + c$
Next i
If carry > 0 Then c$ = Str$( carry ) + c$
End Sub

Sub min( a$ , b$, c$ ) ' given a$ and b$, returns the difference in c$
Local a1$, b1$, h$, i, hold, borrow
c$="" : s$="" :a1$=a$ : b1$=b$ ' initialise variables and preserve a$ and b$
samelen a1$ , b1$
If a1$<b1$ Then ' if result is going to be negative, swap a1 & b1
h$ = a1$
a1$ = b1$
b1$ = h$
s$="-"
EndIf
For i = Len( a1$ ) To 1 Step -1
hold = Val( Mid$( a1$ , i , 1 ) ) - Val( Mid$( b1$ , i , 1 ) ) + 10 - borrow
borrow = 1- Int( hold / 10 )
c$ = Str$( hold Mod 10 ) + c$
Next i
trim c$
c$ = s$+c$ ' add the sign
End Sub

Sub big( a$, b$, biggest ) ' biggest = 1 if a$ >= b$
Local a1$, b1$ 'preserve a$ and b$
a1$ = a$ : b1$ = b$
biggest = 0
samelen (a1$ , b1$)
If a1$>=b1$ Then biggest = 1
End Sub

Sub trim (a$) ' given a$, leading zeros are stripped. a$ is altered.
Local s$
s$=""
If Left$(a$,1)="-" Then ' if the number is negative, preserve the sign
s$="-"
a$=Mid$(a$,2)
EndIf
Do While Left$(a$,1)="0" ' strip leading characters while they are "0"
a$=Mid$(a$,2)
Loop
If a$="" Then a$="0"
a$=s$+a$ ' replace the sign
End Sub


Jim
VK7JH
MMedit   MMBasic Help
 
shoebuckle
Senior Member

Joined: 21/01/2012
Location: Australia
Posts: 189
Posted: 12:35am 07 Feb 2012
Copy link to clipboard 
Print this post

TassyJim,
Would you like me to put this code in the User Library as a demonstration of MMBasic code?
Cheers,
Hugh
 
TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6098
Posted: 12:40am 07 Feb 2012
Copy link to clipboard 
Print this post

  shoebuckle said   TassyJim,
Would you like me to put this code in the User Library as a demonstration of MMBasic code?
Cheers,
Hugh

Yes.
I was going to submit it eventually.
Converting from by usual Basic subroutines to MM Basic was interesting.
I think the code here should be a useful example of how they work.
Jim
VK7JH
MMedit   MMBasic Help
 
shoebuckle
Senior Member

Joined: 21/01/2012
Location: Australia
Posts: 189
Posted: 12:59am 07 Feb 2012
Copy link to clipboard 
Print this post


What file name would you like? Possibilities I thought of are BIGINT.BAS or FACTOR55.BAS but the choice is yours.
Cheers,
Hugh
 
TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6098
Posted: 02:34am 07 Feb 2012
Copy link to clipboard 
Print this post

  shoebuckle said  
What file name would you like? Possibilities I thought of are BIGINT.BAS or FACTOR55.BAS but the choice is yours.
Cheers,
Hugh


BIGINT.BAS is the most appropriate.
The factorial bit is only a test of the functions.

Jim

VK7JH
MMedit   MMBasic Help
 
shoebuckle
Senior Member

Joined: 21/01/2012
Location: Australia
Posts: 189
Posted: 02:53am 07 Feb 2012
Copy link to clipboard 
Print this post

It will be in the next User Library update.
Hugh
 
Print this page


To reply to this topic, you need to log in.

© JAQ Software 2024