Class new title: Natural
	subclassof: String
	fields: ''
	declare: 'Naturalzero ';
	bytesize: false

 t1 
	[super length < t1  [0]
	super  t1]

asInteger 
	[self length = 1  [self  1]
	LargeInteger new bytes: self neg: false]

classInit 
	[Naturalzero _ Natural new: 1.
	Naturalzero  1 _ 0]

isLarge 
	[false]

natadd: t1 | t2 t3 t4 t5 t6  
	[t5 _ MachineDouble init.
	[self length < t1 length 
		[t3 _ t1.
		t2 _ self]
	t3 _ self.
	t2 _ t1].
	t6 _ Natural new: t3 length.
	for t4 to: t3 length do
		[t5 increaseby: t3  t4.
		t5 increaseby: t2  t4.
		t6  t4 _ t5 extract].
	[t5 low  0 
		[t6 _ t6 growby: 1.
		t6 last_ t5 low]].
	t6]

natcompare: t1 | t2 t3 t4  
	[t3 _ self length.
	t3 > t1 length  [3]
	t3 < t1 length  [1]
	for t2 from: self length to: 1 by: 1 do
		[t4 _ self  t2.
		t4 > (t1  t2)  [3]
		t4 < (t1  t2)  [1]].
	2]

natdiv: t1 | t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19    
	[t16 _ self length - t1 length + 1.
	t16 
 0  [Naturalzero , self]
	t5 _ 8 - t1 last hibit.
	t3 _ self natnormalize: t5.
	t6 _ t1 natnormalize: t5.
	t2 _ Natural new: t16.
	t11 _ t6 length - 1.
	t4 _ t16.
	t7 _ t6  t11.
	t8 _ [t11 = 1  [0]
			t6  (t11 - 1)].
	t9 _ MachineDouble init.
	t10 _ MachineDouble new.
	for t15 to: t4 do
		[t14 _ t3 length + 1 - t15.
		t9 high_ t3  t14.
		[t9 high = t7  [t12 _ 1]
		t9 low_ t3  (t14 - 1).
		t12 _ t9 mdiv: t7.
		t9 low_ [t14 < 3  [0]
		t3  (t14 - 2)].
		t10 gets: t12 mtimes: t8.
		t19 _ true.
		while (t9 < t10 and t19) do
			[t12 _ t12 unsignedadd: 1.
			t10 decreaseby: t8.
			t10 high < t7  [t19 _ false]
			t10 high_ t10 high - t7]].
		t16 _ t14 - t11.
		t10 init.
		t17 _ 0.
		for t13 to: t6 length do
			[t9 gets: t12 mtimes: t6  t13.
			t10 increaseby: t3  t16.
			t10 decreaseby: t17.
			t10 decreaseby: t9 low.
			t17 _ t9 high.
			t3  t16 _ t10 extract.
			t16 _ t16 + 1].
		[t10 low = 255 
			[t12 _ t12 unsignedadd: 1.
			t16 _ t14 - t11.
			t9 init.
			for t13 to: t6 length do
				[t9 increaseby: t3  t16.
				t9 increaseby: t6  t13.
				t3  t16 _ t9 extract.
				t16 _ t16 + 1]]].
		t2  t2 length + 1 - t15 _ t12].
	t3 _ t3 natunnormalize: t5 lookfirst: t11.
	[t2 last = 0 
		[t4 < 2  []
		t2 _ t2 growby: 1]].
	t2 , t3]

natdivideandCarry: t1 extra: t2 | t3 t4 t5  
	[t5 _ t2  2.
	t5 high_ 0.
	t4 _ t2  1.
	for t3 from: t4 to: 1 by: 1 do
		[t5 low_ self  t3.
		self  t3 _ t5 mdiv: t1].
	[self  t4 = 0 
		[t4 _ t4 - 1.
		t4 = 0  [t4 _ 1]]].
	t2  1 _ t4.
	t5 high]

natnormalize: t1 | t2 t3 t4 t5 t6  
	[t4 _ Natural new: self length + 1.
	t2 _ 0.
	t5 _ t1 - 8.
	for t3 to: t4 length do
		[t6 _ self  t3.
		t4  t3 _ ((t6 lshift: t1) lor: t2) land: 255.
		t2 _ t6 lshift: t5].
	t4]

natsubtract: t1 | t2 t3 t4 t5 t6 t7 t8 t9 t10   
	[t7 _ self length.
	t8 _ t1 length.
	t5 _ MachineDouble init.
	[t7 = t8 
		[t4 _ t7.
		while (self  t4 = (t1  t4) and t4 > 1) do
			[t4 _ t4 - 1].
		t7 _ t4.
		self  t4 unsignedlessthan: t1  t4 
			[t3 _ t1.
			t9 _ true.
			t2 _ self]
		t3 _ self.
		t2 _ t1.
		t9 _ false]
	t7 < t8 
		[t3 _ t1.
		t2 _ self.
		t9 _ true.
		t7 _ t8]
	t3 _ self.
	t2 _ t1.
	t9 _ false].
	t6 _ Natural new: t3 length.
	t10 _ 1.
	for t4 to: t3 length do
		[t5 increaseby: t3  t4.
		t5 decreaseby: t2  t4.
		(t6  t4 _ t5 extract)  0  [t10 _ t4]].
	[t10 = t3 length  []
	t5 _ Natural new: t10.
	for t4 to: t10 do
		[t5  t4 _ t6  t4].
	t6 _ t5].
	LargeInteger new bytes: t6 neg: t9]

nattimes: t1 | t2 t3 t4 t5 t6 t7 t8 t9    
	[self length = 1 and self  1 = 0  [Naturalzero]
	t4 _ self length + t1 length.
	t2 _ Natural new: t4.
	t3 _ MachineDouble new.
	for t7 to: t4 do
		[t2  t7 _ 0].
	for t7 to: self length do
		[t9 _ t7 - 1.
		t5 _ 0.
		t6 _ self  t7.
		t6  0 
			[for t8 to: t1 length do
				[t3 gets: t6 mtimes: t1  t8.
				t3 increaseby: t5.
				t9 _ t9 + 1.
				t3 increaseby: t2  t9.
				t2  t9 _ t3 low.
				t5 _ t3 high].
			t2  t9 + 1 _ t5]].
	t2  t4 = 0  [t2 growby: 1]
	t2]

natunnormalize: t1 lookfirst: t2 | t3 t4 t5 t6 t7  
	[t1 _ 0 - t1.
	t3 _ 0.
	t6 _ t1 + 8.
	t4 _ t2.
	t7 _ self  t4.
	while (((t7 lshift: t1) lor: t3) = 0 and t4  1) do
		[t3 _ t7 lshift: t6.
		t4 _ t4 - 1.
		t7 _ self  t4].
	t5 _ Natural new: t4.
	t2 _ t4.
	t3 _ self  1 lshift: t1.
	for t4 to: t2 do
		[t7 _ self  (t4 + 1).
		t5  t4 _ (t7 lshift: t6) lor: t3.
		t3 _ t7 lshift: t1].
	t5]

printon: t1 
	[self printon: t1 base: 10]

printon: t1 base: t2 | t3 t4 t5 t6 t7 
	[t3 _ Stream default.
	t4 _ self length , MachineDouble new.
	t5 _ Natural new: super length.
	t6 _ t2 * t2.
	self copyto: t5.
	until (t4  1 = 1 and t5  1 < t6) do
		[t7 _ t5 natdivideandCarry: t6 extra: t4.
		t3 next_ t7 \ t2 + 48.
		t3 next_ t7 / t2 + 48].
	t5  1 printon: t1 base: t2.
	t1 append: t3 contents reverse]

species 
	[Natural]