Huge #'s

mike74 · Post by **mike74** » Thu Jul 19, 2007 4:25 pm

Michael,

Your GetNumber works if you replace

*s=t

with

CopyMemory(@t, *s, Len(t))

Michael Vogel · Post by **Michael Vogel** » Thu Jul 19, 2007 4:48 pm

mike74 wrote:CopyMemory(@t, *s, Len(t))

Hi Mike,

PB4.02 brings up an error, that a number is expecteted instead of a string...

If I do a debug *s in the procedure, I'll see an (empty) string, s=0, @*s=0, @s=address

Changing the *s parameter in the CopyMemory to anything else, I'll get a memory access error...

Therefore I've never got clear with pointers

mike74 · Post by **mike74** » Thu Jul 19, 2007 4:57 pm

I'm using the PB 4.0 Beta for Mac. Maybe there are one or more bugs involved. Be careful not to write to any random memory address! You can mess up your computer big time!

mike74 · Post by **mike74** » Thu Jul 19, 2007 5:19 pm

Michael,

I just realized I had made another change...

Take the ".s" off the *s.s in the procedure. Sorry!

Michael Vogel · Post by **Michael Vogel** » Thu Jul 19, 2007 5:27 pm

mike74 wrote:Michael,

I just realized I had made another change... Take the ".s" off the *s.s in the procedure. Sorry!

Why sorry, you're trying to help me

Anyway, I'm not clever enough to bring it up running

Actual error: Destination memory pointer is 0

Actual question: would the CopyMemory command reserve new memory for the variable which will be kept (in case of things like garbage collection)?

Code: Select all

Procedure GetNumber(*s,*num.VNF)
	Protected n
	Protected t.s

	If *num\sign
		t="-"
	EndIf

	n=*num\len
	t+Str(*num\num[n])

	While n>0
		n-1
		t+RSet(Str(*num\num[n]),#VNFLen,"0")
	Wend

	CopyMemory(@t,*s,Len(t))

EndProcedure

mike74 · Post by **mike74** » Thu Jul 19, 2007 5:34 pm

Actual answer: I don't know...

I would think not, but I really don't know.

Did you initialize your Zahl3 variable with a value like PDwyer suggested?

Michael Vogel · Post by **Michael Vogel** » Thu Jul 19, 2007 5:44 pm

mike74 wrote:Actual answer: I don't know... I would think not, but I really don't know.

Did you initialize your Zahl3 variable with a value like PDwyer suggested?

Okay

When I initialize zahl3 (e.g. zahl=space(1000)) than my initial version (*s=t) seems to work fine - but what is going on in the memory?

Do I have produced a memory leak, when assigning the shorter content "t" to the larger "s" space? How can this be done (= programmed) correctly? Where are the real experts?

Because I'm not able to do so, I made the routine Number() :roll:

Michael

mike74 · Post by **mike74** » Thu Jul 19, 2007 5:58 pm

I don't know how it works with *s = t, but you're right as far as CopyMemory goes -- you need to make sure that the memory area being copied to is big enough (or use MoveMemory, which is supposedly slower). The PB Help file has some info.

Demivec · Post by **Demivec** » Thu Jul 19, 2007 6:46 pm

@Michael Vogel:

The "GetNumber" procedure can be handled in a simple way. You can replace it with your "Number" procedure and use it this way:

Code: Select all

;instead of 
zahl3.s
GetNumber(@zahl3,@num1)
;use
zahl3.s=Number(num1) ;just rename this to "GetNumber"

You have a more serious problem with the VNFMul(*a.VNF,*b.VNF,*c.VNF) procedure.

It fails with factors whose digits produce large carry's. This happens with 2 factors as small as "99999" and "99999". This means that if a group of these digits appears in both factors the product will be wrong One example is "10000999990" and "99999000000". The result should be "1000089998000010000000" but your routine returns "1000089998000". The routine I used (provided by Helle acutally) can handle 2 factors of at least 11111 digits that are all 9's.

mike74 · Post by **mike74** » Thu Jul 19, 2007 9:16 pm

Another variation of Demivec's code:

Code: Select all

Procedure.s MultiplyBig(factor_1$,factor_2$) ;returns Prod$ as factor_1$*factor_2$, factors can have leading zeroes and be negative
 
  Protected n.l,len_factor_1.l,len_factor_2.l,len_diff.l
 
  len_factor_1 = Len(factor_1$)
  len_factor_2 = Len(factor_2$)
  If len_factor_2 > len_factor_1 ;make it so larger# is always factor_1
    Swap factor_1$,factor_2$
    Swap len_factor_1,len_factor_2
  EndIf
  n = len_factor_1
  len_diff = n - len_factor_2 + 1
 
  Protected n_2.l = n + n
  Protected Dim factor_1.l(n)
  Protected Dim prod.l(n_2)
  Protected Prod$,I.l,J.l,s.l,temp.l,factor_2_sub_I.l, z.l
  prod$ = Space(n_2)
 
  z = 0
  For I = len_diff To n    ;digit# for factor_1
    factor_2_sub_I = PeekB(@factor_2$ + z) - 48
    z + 1
    If factor_2_sub_I > 0
      For J = 1 To n       ;digit# for factor_2
        prod(I + J) + (PeekB(@factor_1$ + J - 1) - 48) * factor_2_sub_I
      Next J
    EndIf
  Next I
  
  temp = 0
  For I = n_2 To len_diff Step -1 ;digits# of product
    z = prod(I) + temp
    temp = Int(z / 10)
    CopyMemory(Str(z - 10 * temp), @prod$ + I - 1, 1)
  Next I

  For I = 0 To (len_factor_1 + len_factor_2) ;digits# of product
    If (PeekB(@prod$ + I) - 48) > 0 ;find first non-zero digit
      prod$ = Right(prod$, Len(prod$) - I)
      Break
    EndIf
  Next I 
  
  If PeekB(@factor_1$) = 45 ;,1) ;get sign of factor_1
    s = 1
  EndIf
 
  If PeekB(@factor_2$) = 45 ;,1) ;combine with sign of factor_2
    s ! 1
  EndIf
 
  If s = 1  ;=sign will be negative
    prod$ = "-" + Prod$
  EndIf
 
  ProcedureReturn Prod$
EndProcedure


F1$="-123456789098765432198765432123456789"
F2$="5555555556666666666777777777777777778765434567654"
StartTime = ElapsedMilliseconds()
For t = 1 To 10000
P$=MultiplyBig(F1$, F2$)
Next t
  ElapsedTime = ElapsedMilliseconds()-StartTime
Debug ElapsedTime
Debug P$

Michael Vogel · Post by **Michael Vogel** » Fri Jul 20, 2007 12:13 am

Demivec wrote:@Michael Vogel:

The "GetNumber" procedure can be handled in a simple way. You can replace it with your "Number" procedure and use it this way:
Code: Select all
;instead of 
zahl3.s
GetNumber(@zahl3,@num1)
;use
zahl3.s=Number(num1) ;just rename this to "GetNumber"
You have a more serious problem with the VNFMul(*a.VNF,*b.VNF,*c.VNF) procedure.

It fails with factors whose digits produce large carry's. This happens with 2 factors as small as "99999" and "99999". This means that if a group of these digits appears in both factors the product will be wrong One example is "10000999990" and "99999000000". The result should be "1000089998000010000000" but your routine returns "1000089998000". The routine I used (provided by Helle acutally) can handle 2 factors of at least 11111 digits that are all 9's.

Hi Demivec, you're cool!

First, I was amused about your "solution" of GetNumber - but to be honest I'm still interested if someone can give me a hint how to get the GetNumber procedure working...

Then, I was really nervous that I've done something wrong (what still can be), but after a quick check I saw that my routine is not only fast but seems also to work fine (at least with your example)

So please check it once more, maybe there's a bug somewhere. But maybe there are other reasons for your wrong results, maybe the PB version does not support quads or the variable for the third parameter is the same variable like one of the multipliers (so VNFMul(@a,@a,@b) is allowed, but VNFMul(@a,@b,@a) not!)

If you need bigger numbers, you've to imcrease #VNFDim (e.g. #VNFDim=10000 to allow numbers with 90000 ciphers;)

I did not a lot of testing, just some benchmarks - but with all examples (for now) I got the same results like Helle & Co...

Code: Select all

num1.VNF
num2.VNF
num3.VNF

TA = ElapsedMilliseconds()
For i = 1 To 10000
	PutNumber(@F1$,@num1)
	PutNumber(@F2$,@num2)
	VNFMul(@num1,@num2,@num3)
Next
TE = ElapsedMilliseconds() - TA
p$=Number(@num3)
DIGIT=Len(p$)
MessageRequester("BCD-Multiply, Test1", P$ + #LFCR$ + "Time : " + Str(TE) + " ms" + #LFCR$ + "Digits : " + Str(DIGIT))


Global F3$ = "2"
TA = ElapsedMilliseconds()
PutNumber(@F3$,@num1)
For i = 1 To 15
	VNFMul(@num1,@num1,@num2)
	VNFCopy(@num2,@num1)
Next
p$=Number(@num2)
DIGIT=Len(p$)
TE = ElapsedMilliseconds() - TA
MessageRequester("Time : " + Str(TE) + " ms   Digits : " + Str(DIGIT), Mid(P$, 2500, DIGIT-2499) + #LFCR$ + "Time : " + Str(TE) + " ms" + #LFCR$ + "Digits : " + Str(DIGIT))

Demivec · Post by **Demivec** » Fri Jul 20, 2007 2:14 am

Here's an update to Helle's code (it has been nicknamed mine for the moment). This takes into account some of mike74's suggestions as well as a few of my own. I estimate it's about twice as fast as before.

Code: Select all

Procedure.s MultiplyBig(factor_1$,factor_2$) ;returns Prod$ as factor_1$*factor_2$, handles negative numbers
  
  Protected n.l,len_factor_1.l,len_factor_2.l
  len_factor_1 = Len(factor_1$)
  len_factor_2 = Len(factor_2$)
  If len_factor_2 > len_factor_1 ;make it so larger# is always factor_1
    Swap factor_1$,factor_2$
    Swap len_factor_1 , len_factor_2
  EndIf
  n=len_factor_1
  CallDebugger
  Protected maxNSize.l = n + len_factor_2,len_diff = len_factor_1 - len_factor_2
  Protected Dim prod.l(maxNSize)
  Protected Prod$=Space(maxNSize),I.l,J.l,adj.l,digit.l,carry.l,s.l
 
  adj.l = -len_diff - 1
  For I = 1 + len_diff To n ;digit# for factor_2
    factor_2_sub_I=PeekB(@factor_2$ + I + adj) & $F ;read next digit from factor_2
    If factor_2_sub_I > 0
      For J = 1 To n ;digit# for factor_1
        prod(I - len_diff + J) + (PeekB(@factor_1$ + J - 1) & $F)* factor_2_sub_I
      Next J
    EndIf
  Next I
  
  For I = maxNSize To 1 Step -1 ;digits# of product
    digit = prod(I) + carry
    carry = Int(digit / 10)
    PokeB(@Prod$ + I - 1,(digit - 10 * carry) | $30)
  Next I
  
  For I = 0 To (maxNSize - 1) ;digits# of product
    If PeekB(@Prod$ + I) > 48 ;find first non-zero digit
      Prod$ = Right(Prod$, maxNSize - I)
      Break
    EndIf
  Next I
  
  If PeekB(@factor_1$) = 45 ;get sign of factor_1
    s = 1
  EndIf
  
  If PeekB(@factor_2$) = 45 ;combine with sign of factor_2
    s ! 1
  EndIf
  
  If s = 1  ;=sign will be negative
    Prod$="-"+Prod$
  EndIf
  
  ProcedureReturn Prod$
EndProcedure 

;-test
; zahl1.s="123456789098765432198765432123456789"
; zahl2.s="5555555556666666666777777777777777778765434567654"

zahl1.s="10000999990"
zahl2.s="99999000000"

; zahl1.s="99999"
; zahl2.s="99999999"

n=1000000
Prod$=""
t1=-GetTickCount_()
For I=1 To n
  Prod$=MultiplyBig(zahl1,zahl2)
Next I
t1+GetTickCount_()
MessageRequester(Str(t1)+" ms For "+Str(n)+" multiplications",zahl1+" x "+zahl2+" = "+#LF$+Prod$)

@Michael Vogel: I think I may have been the bug in your code. I was trying to improve it's speed and I think I made a wrong turn

.
I couldn't test your new sample because I didn't have the VFNCopy procedure.

Since you really want GetNumber your way (instead of the easy way

) use this:

Code: Select all

Procedure GetNumber(*s.String,*num.VNF)
  Protected n
  Protected T.s
  
  If *num\sign
    T="-"
  EndIf
  
  n=*num\len
  T+Str(*num\num[n])
  
  While n>0
    n-1
    T+RSet(Str(*num\num[n]),#VNFLen,"0")
  Wend
  
  *s\s=T;   Does work!!!!
  
EndProcedure

zahl3.String ;use a structure for a string
GetNumber(@zahl3,@num1)
Debug zahl3\s

One additional note, when you pass a structure such as num1 or zahl3 (in my example) you don't need to use @. The address is all that will be sent whether or not you use @.

mike74 · Post by **mike74** » Fri Jul 20, 2007 2:49 am

Rather than continue to post new versions here, I've posted my version to a wikispaces page. I'll still report significant updates here, if there are any. Also, the page has an RSS feed. The page is at http://mike74swiki.wikispaces.com/Big+Multiply and the RSS feed is http://mike74swiki.wikispaces.com/page/ ... ?v=rss_2_0.

The latest version works for negative numbers and chooses between two looping methods to reduce the number of operations as much as possible, based on the number of zeros in the numbers and the numbers' lengths.

Michael Vogel · Post by **Michael Vogel** » Fri Jul 20, 2007 8:42 am

Demivec wrote: @Michael Vogel:
[1] I couldn't test your new sample because I didn't have the VFNCopy procedure.

[2] Since you really want GetNumber your way (instead of the easy way ) use this:
Code: Select all
Procedure GetNumber(*s.String,*num.VNF)
  Protected n
  Protected T.s
  
  If *num\sign
    T="-"
  EndIf
  
  n=*num\len
  T+Str(*num\num[n])
  
  While n>0
    n-1
    T+RSet(Str(*num\num[n]),#VNFLen,"0")
  Wend
  
  *s\s=T;   Does work!!!!
  
EndProcedure

zahl3.String ;use a structure for a string
GetNumber(@zahl3,@num1)
Debug zahl3\s
[3] ...you don't need to use @...

Hi Demivec,

thanks for your reply, for [1] you'll can see the actual code below - I think it's about 5 to 10 times faster than all other routines - I would be happy of course if someone will be able to tune it a little bit

I've also include a Add and Sub procedure now (not very well tested for now), so next step would be Div...
Hopefully, all routines work with positive and negative integers.

[2] - I can't get it running, I entered all changes (.String and \s) but there's still an error when running (Null pointer), I'm using PB4.02 Win -- you're right, Number() is doing the same, but there are things I just want to know how it can be done

[3] - Thanks again, looks better when reading the source...

And here's the "full" code (sorry for the long postings, mikes idea with a wiki is a clever thing) - now the benchmark from the last post will run...

Code: Select all

; Define VNF - Vogels Number Format

	#VNFDim=10000; ~90000 Ciphers ;)

	#VNFLen=9
	#VNFMod=1000000000

	#VNFNegative=-1
	#VNFPositive=0

	Structure VNF
		len.w
		sign.w
		num.l[#VNFDim]
	EndStructure

	Declare.s Number(*num.VNF);						String
	Declare GetNumber(*s.s,*num.VNF);			s <- num
	Declare PutNumber(*s.s,*num.VNF);			s -> num
	
	Declare VNFNormalize(*a.VNF);					a = (a)
	Declare VNFCopy(*a.VNF,*b.VNF);				b = a

	Declare VNFMul(*a.VNF,*b.VNF,*c.VNF);	c = a*b
	Declare VNFAdd(*a.VNF,*b.VNF,*c.VNF);	c = a+b
	Declare VNFSub(*a.VNF,*b.VNF,*c.VNF);	c = a-b

	Declare.l VNFGt(*a.VNF,*b.VNF);				true, if a>b
	Declare.l VNFEq(*a.VNF,*b.VNF);				true, if a=b

; EndDefine

Procedure.s Number(*num.VNF)

	Protected n
	Protected t.s

	If *num\sign
		t="-"
	EndIf

	n=*num\len
	t+Str(*num\num[n])

	While n>0
		n-1
		t+RSet(Str(*num\num[n]),#VNFLen,"0")
	Wend

	ProcedureReturn t

EndProcedure
Procedure GetNumber(*s.String,*num.VNF)

	; ACHTUNG! s ist bei dieser Routine vom Typ String!
	; (bei x.string bedeutet dies den Aufruf "GetNumber(x,number)" und die Ausgabe "Debug x\s")

	Protected n
	Protected t.s

	If *num\sign
		t="-"
	EndIf

	n=*num\len
	t+Str(*num\num[n])

	While n>0
		n-1
		t+RSet(Str(*num\num[n]),#VNFLen,"0")
	Wend

	*s\s=t

EndProcedure
Procedure PutNumber(*s.s,*num.VNF)

	Protected n,p
	Protected t.s

	*num\sign=0

	t=PeekS(@*s)
	n=Len(t)-#VNFLen

	While n>0
		*num\num[p]=Val(PeekS(@t+n,#VNFLen))
		p+1
		n-#VNFLen
	Wend

	n=Val(PeekS(@t,9+n))
	If n<0
		*num\sign=#VNFNegative
		n=-n
	EndIf

	*num\num[p]=n

	*num\len=p

EndProcedure

Procedure VNFNormalize(*a.VNF)
	; Strap leading zeros (000.000.000)
	While (*a\len>=0) And (*a\num[*a\len]=0)
		*a\len-1
	Wend
	; Value equal Zero? Positiv sign
	If *a\len<0
		*a\len=0
		*a\sign=#VNFPositive
	EndIf
EndProcedure
Procedure VNFCopy(*a.VNF,*b.VNF)
	Protected n=*a\len

	*b\len=n
	*b\sign=*a\sign

	Repeat
		*b\num[n]=*a\num[n]
		n-1
	Until n<0

EndProcedure

Procedure.l VNFEq(*a.VNF,*b.VNF)

	Protected n,d

	If n<>*b\len
		ProcedureReturn #False
	ElseIf *a\sign<>*b\sign
		ProcedureReturn #False
	Else
		While n>=0
			If *a\num[n]<>*b\num[n]
				ProcedureReturn #False
			EndIf
			n-1
		Wend
		ProcedureReturn #True;	a=b
	EndIf

EndProcedure
Procedure.l VNFGt(*a.VNF,*b.VNF)

	Protected n,d

	If *a\sign<>*b\sign
	
		If *a\sign=#VNFPositive
			ProcedureReturn #True
		Else
			ProcedureReturn #False
		EndIf
	
	Else
	
		n=*a\len
		If n>*b\len
			ProcedureReturn #True
		ElseIf n<*b\len
			ProcedureReturn #False
		Else
			While n>=0
				d=*a\num[n]-*b\num[n]
				If d>0
					ProcedureReturn #True
				ElseIf d<0
					ProcedureReturn #False
				EndIf
				n-1
			Wend
			ProcedureReturn #False;	a=b
		EndIf
		
	EndIf
	
EndProcedure

Procedure VNFMul(*a.VNF,*b.VNF,*c.VNF)

	Protected la
	Protected lb
	Protected n

	Protected s.q
	Protected z.q

	*c\sign=-(*a\sign * *b\sign)
	*c\len=*a\len+*b\len+1
	For n=0 To *c\len
		*c\num[n]=0
	Next n

	la=0
	Repeat
		lb=0
		z=*b\num[lb]
		Repeat
			s=*a\num[la] * *b\num[lb] + *c\num[la+lb]
			;Debug Str(*a\num[la])+" * "+Str(*b\num[lb])+" + "+Str(*c\num[la+lb+1])
			;Debug " = "+StrQ(s)+"  -> "+Str(s/#VNFMod)+" | "+Str(s%#VNFMod)
			*c\num[la+lb]=s%#VNFMod
			*c\num[la+lb+1]+s/#VNFMod
			lb+1
		Until lb>*b\len
		la+1
	Until la>*a\len

	VNFNormalize(*c)

EndProcedure
Procedure VNFAdd(*a.VNF,*b.VNF,*c.VNF)

	Protected n
	Protected s

	If *a\sign<>*b\sign
		;Debug "sub"
		*b\sign=*a\sign
		VNFSub(*a.VNF,*b.VNF,*c.VNF)
	Else

		*c\sign=*a\sign

		If *a\len<*b\len
			Swap *a,*b
		EndIf

		While n<=*a\len
			s+*a\num[n]
			If n<=*b\len
				s+*b\num[n]
			EndIf
			*c\num[n]=s%#VNFMod
			s/#VNFMod
			n+1
		Wend
		If s
			*c\num[n]=s
		Else
			n-1
		EndIf

		*c\len=n
	EndIf

EndProcedure
Procedure VNFSub(*a.VNF,*b.VNF,*c.VNF)

	Protected n
	Protected s

	If *a\sign<>*b\sign
		;Debug "add"
		*b\sign=*a\sign
		VNFAdd(*a.VNF,*b.VNF,*c.VNF)
	Else

		If VNFGt(*a.VNF,*b.VNF)
			*c\sign=*a\sign
		Else
			;Debug "swp"
			Swap *a,*b
			*c\sign=#VNFNegative-*a\sign
		EndIf


		While n<=*a\len
			s+*a\num[n]
			If n<=*b\len
				s-*b\num[n]
			EndIf
			If s<0
				*c\num[n]=s+#VNFMod
				s=-1
			Else
				*c\num[n]=s
				s=0
			EndIf
			n+1
		Wend

		*c\len=n-1

		VNFNormalize(*c)

	EndIf

EndProcedure

num1.VNF
num2.VNF
num3.VNF

;zahl1.s="123456789098765432198765432123456789"
zahl1.s="5555555556666666666777777777777777778765434567654"
zahl2.s="-5555555556666666666777777777777777778765434567653"

PutNumber(@zahl1,num1)
PutNumber(@zahl2,num2)

VNFAdd(num1,num2,num3)

Debug Number(num3)

Updated code - 22. July 2007

Demivec · Post by **Demivec** » Fri Jul 20, 2007 4:37 pm

Michael Vogel wrote:[2] - I can't get it running, I entered all changes (.String and \s) but there's still an error when running (Null pointer), I'm using PB4.02 Win -- you're right, Number() is doing the same, but there are things I just want to know how it can be done

I'm use PB4.02 Win also. What do you mean that there's an error using Null pointer? I thought the example I gave included a Null pointer.

Regarding long postings, PM me and we'll post highlights here. (I don't know anything about setting up Wiki's). I am interrested in finding a fast and versatile way for using big #'s. Yes, I've heard there's some out there somewhere, but a PB one would be nice. I had done optimizations on PutNumber, GetNumber, and was working on VNFMult before I made a wrong turn.