PureBasic Forums - English

Posted: **Mon Feb 11, 2008 5:05 pm**

Hello at all.

Somebody know a link for make a pow(a,b) but without restriction of size.

Example :

MegaPow(1538422836, 831387343544)

And it was christmas, if you have the invert of this function.

Also i search a code that with a giant number, give the more little 2 number possible with POW()

Exemple:

Code: Select all

POW(a, b)=123873743543737379479382744947316546127612741762167241624721465875215472165247126472134712837212576216821628762861237217621971500107017108195

What is the more little number a and b possible for approach this result.
And how many is the rest, if the result of POW(a,b) is not perfect.

Thanks for your help

Posted: **Mon Feb 11, 2008 5:34 pm**

The size restriction isn't in the pow() function, it's in the datatype. How are you planning to store these giant numbers?

Posted: **Mon Feb 11, 2008 5:58 pm**

This giant number is a string.

This is the result of convert a key in ASCII number, for replace the letter by a number.
This is a random exemple :

Code: Select all

Afag25dGhdegfhtrrszzazejfRFDEFZà0 = 65102971035053100711041001011031021041161141141151221229712210110610282706869709022448

I'm a oyster in mathematical

I don't know how i can do

By using the strings, I got to create very large multiplication and division with 100 number, but use the root is too hard for me

Posted: **Mon Feb 11, 2008 9:41 pm**

I move a little bit

If Pow(14, 6) = 7529536
And Round(Pow(7529536, (1/6)), 1) = 14

Until the all goes well

I want do this operation in two parts
For example with 7529000 and 536 = 7529536
for have obviously the same result

If 7529000 + 536 = 7529536
But Round(Pow(7529000, (1/6)), 1) + Round(Pow(536, (1/6)), 1) = 17

And me i search 14 tor result

Where i have made a mistake ?

Posted: **Mon Feb 11, 2008 9:50 pm**

You can't split a number and take seperate roots or powers and get the right result, it just doesn't work like that.

For example:

sqr(25) + sqr(16) is not equal to sqr(25+16).

Posted: **Mon Feb 11, 2008 10:30 pm**

Thanks dereck

But how can i do for add number after number and have a correct result for 7529536

Root of 536
Root of 29000
Root of 7500000

Why i have not learn at school

Posted: **Mon Feb 11, 2008 10:31 pm**

@Kwaï chang, you can find some lib in http://www.purearea.net/ which can manage big numbers, and also make depp maths operations with it.

Talking about big numbers may you like take a read to this:
http://en.wikipedia.org/wiki/Googol

Posted: **Tue Feb 12, 2008 12:19 am**

@Kwaï chang, you can find some lib in http://www.purearea.net/ which can manage big numbers, and also make depp maths operations with it.

Thanks psychofanta.
I found 2 lib in the link you gave me : LongValuesString and MathExtra this is this lib that you talk me ?
I am not sure that calculate big number, when i read the doc :roll:

http://en.wikipedia.org/wiki/Googol

It's funny googol, i learn it was the begin of Google and a big number.
But my problem is always full

Posted: **Tue Feb 12, 2008 1:01 am**

There's some code here

http://www.purebasic.fr/english/viewtop ... c&start=15

My code to do powers though can handle pretty much any number size as the first parameter but the power only supports a long. You could change this to a quad if you like but you will probable find that the answer to "MegaPow(1538422836, 831387343544)" is not going to fit into memory

The function on that page is: Procedure.s BigPow(Num.s, pow.l) which has the dependant function: Procedure.s BigMultiply(Num1.s,Num2.s)
(It's faster than just muliplying pow times though.

Posted: **Tue Feb 12, 2008 10:09 am**

Thank you very much PDWYER.
It's a big move for me.

But i don't understand, why you are restrict the second character by a long ?

And i also search to do a BigRoot, invert of BigPow.
Have you that, in your big drawer of code ?

Posted: **Tue Feb 12, 2008 10:43 am**

When I use bigPow("1538422836", 1000) (your number in the top example for the first digit) then answer is 9,188 digits long. If I make this to the power of 10,000 the answer is 91,871 digits long and takes a little while to run. I'll admit that there is other code in the PB forum that runs quite a bit faster for multiplication and there might be shortcuts for pow() but at this rate using a long with power 2,000,000,000 the answer is going to be a 180gb string which if I had enough memory to hold would take days to finish but since I only have 2gb it's going to page to disk then PB string limitations will crash it

!!

I'll write you a 64bit version when PB comes out with a 64bit compiler that handles 64bit long strings and I can address 64bits of memory and have a few more gigs in my PC

(or I'll run it on a big dev server at work).

As for root() I haven't done that yet. Partly because I'm not sure how it's done, I haven't read through this yet http://en.wikipedia.org/wiki/Square_root and also because my bigint.pbi only handles positive integers and no negatives or decimals. Getting the sqr() of 2 is going to be as long as you let it I guess. If you are using strings with arbitrarily long numbers how far do you calc it? take a second param for the rounding I guess. Sounds interesting but also a lot of work, and I don't need it at the moment

Posted: **Tue Feb 12, 2008 11:26 am**

Hi,

maybe I drifted already away from the initial target*, but I programmed and (not very) fast version for doing Pow(a,b) with nicely big numbers...

But, it's not very fast, you have to wait around 30 seconds (with enabled debugger) for the calculation of 1538422836^10000...

Here is my code (with some additionally needed routines of my VNF project):

Code: Select all

; Version 0.5.0

; Define VNF - Vogels Number Format


	#VNFDim=25000; ~225000 Ciphers ;)

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

	; Signs
	#VNFNegative=1
	#VNFPositive=0

	; Errortypes (len-field)
	#VNFUndefined=-1
	#VNFInfinitive=-2
	#VNFOverflow=-3
	#VNFNotImplemented=-4

	; Dimensions
	#VNFLen=9
	#VNFMod=1000000000

	Global VNF_Cache_A.VNF
	Global VNF_Cache_B.VNF
	Global VNF_Cache_C.VNF

; EndDefine

Procedure.s Number(*num.VNF)

	Protected n
	Protected t.s

	If *num\len<0

		Select *num\len
		Case #VNFUndefined
			t="Undefined"
		Case #VNFInfinitive
			t="Infinitive"
			If *num\sign
				t="Minus "+t
			EndIf
		Case #VNFOverflow
			t="Overflow"
		Case #VNFNotImplemented
			t="Not Implemented"
		EndSelect

	Else

		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

	EndIf

	ProcedureReturn t

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

	Protected n,p
	Protected t.s

	*num\sign=#VNFPositive

	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)
	If *a\len>=0
		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
	EndIf
EndProcedure
Procedure VNFError(type,stype,*a.VNF)

	If type>=0
		type=stype
	EndIf

	Debug "ERROR "+Str(type)
	*a\len=type

EndProcedure
Procedure VNFCopy(*a.VNF,*b.VNF)
	Protected n

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

	While n>=0
		*b\num[n]=*a\num[n]
		n-1
	Wend

EndProcedure
Procedure VNFAbs(*a.VNF)
	*a\sign=#VNFPositive
EndProcedure

Procedure.l VNFPositive(*a.VNF)

	If *a\sign=#VNFPositive
		ProcedureReturn #True
	Else
		ProcedureReturn #False
	EndIf

EndProcedure

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

	Protected n
	Protected m.q

	n=*a\len

	If n<0
		VNFError(n,0,*c.VNF)
	Else

		If b=0
			*c\len=0
			*c\sign=#VNFPositive
			*c\num[0]=0
		Else

			If b<0
				b=-b
				*c\sign=#VNFNegative-*a\sign
			Else
				*c\sign=*a\sign
			EndIf

			n=0
			Repeat
				m+*a\num[n] * b
				*c\num[n]=m%#VNFMod
				m/#VNFMod

				n+1
			Until n>*a\len

			If m
				*c\num[n]=m
			Else
				n-1
			EndIf
			*c\len=n

		EndIf
	EndIf

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

	Protected la
	Protected lb
	Protected n

	Protected s.q
	Protected z.q

	If (*a\len<0) Or (*b\len<0)
		VNFError(*a\len,*b\len,*c.VNF)
	Else
		*c\sign=(*a\sign + *b\sign)&1;	because #VNFNegative=1
		*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]
				*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)

	EndIf
EndProcedure
Procedure VNFSqr(*a.VNF)
	If *a\len>=0
		VNFMul(*a,*a,VNF_Cache_C)
		VNFCopy(VNF_Cache_C,*a)
	EndIf
EndProcedure
Procedure VNFPow(*a.VNF,b,*c.VNF)

	Protected z=0,s,sign

	If b<0

		; a^b | b<0 not implemented for now...
		VNFError(#VNFNotImplemented,0,*c.VNF)

	ElseIf *a\len>=0

		VNFCopy(*a,VNF_Cache_A)
		PutNumber(@"1",VNF_Cache_B)

		If VNFPositive(*a)=#False
			VNFAbs(VNF_Cache_A)
			If b&1 : VNF_Cache_B\Sign=#VNFNegative : EndIf
		EndIf

		While b>0
			s=1<<z
			If b&s
				VNFMul(VNF_Cache_A,VNF_Cache_B,VNF_Cache_C); *1
				VNFCopy(VNF_Cache_C,VNF_Cache_B); *2
				b-s
			EndIf

			If b
				VNFSqr(VNF_Cache_A)
				z+1
			EndIf

		Wend

		VNFCopy(VNF_Cache_B,*c)

	EndIf
EndProcedure

x.VNF
y.VNF
z.VNF

time=-GetTickCount_()

	PutNumber(@"2",x)
	VNFPow(x,1000,z)
	Debug "2^1000="+Number(z)
	
	PutNumber(@"1538422836",x)
	VNFPow(x,10000,z)
	Debug "Lenght of 1538422836^10000: "+Str(Len(Number(z)))

time+GetTickCount_()
Debug ""
Debug "Calculation time was "+Str(time)+" ms"

For clever guys

... I didn't want to use (many of the) global variables VNF_Cache, but things, like VNFMul(VNF_Cache_A,*c,*c) instead of lines *1 andf *2 did not work - anyone sees why?

For very clever guys

... I didn't look into math books for creating the power function, so maybe there are possibilities to use a better approach...

_________________
*) if factorizing is the real target, forget it! RSA is based on the fact, that finding the dividers of huge numbers is a time consuming work...

Posted: **Tue Feb 12, 2008 11:34 am**

Apparently you can use Fast Fourier transforms to do this lots quicker.

Except I don't understand Fast Fourier transforms

That said, even if you do it quicker, where to you get the space?

Posted: **Tue Feb 12, 2008 11:41 am**

pdwyer wrote:Apparently you can use Fast Fourier transforms to do this lots quicker.

Except I don't understand Fast Fourier transforms

That said, even if you do it quicker, where to you get the space?

Hi pdwyer, give me a hint, please...
...what is done quicker?

Posted: **Tue Feb 12, 2008 12:32 pm**

One thousand thanks at you two

I don't know how i can thanks you

I am looking for this solution for 5 days

For do the root, like 2V5 = pow(2, 1/5)

Your function run always ?, if i write :

Code: Select all

VNFPow(x, val(BigDivide(1, y)), z)

Or that :

Code: Select all

BigPow(x, val(BigDivide(1, z)))

If val(BigDivide(1, z)) is not too long, for a long variable

Or i will have problems sometimes :roll:

PureBasic Forums - English

MegaPow(), i need superman mathematical

MegaPow(), i need superman mathematical