-- This file is  free  software, which  comes  along  with  SmartEiffel. This
-- software  is  distributed  in the hope that it will be useful, but WITHOUT
-- ANY  WARRANTY;  without  even  the  implied warranty of MERCHANTABILITY or
-- FITNESS  FOR A PARTICULAR PURPOSE. You can modify it as you want, provided
-- this header is kept unaltered, and a notification of the changes is added.
-- You  are  allowed  to  redistribute  it and sell it, alone or as a part of
-- another product.
--       Copyright (C) 1994-2002 LORIA - INRIA - U.H.P. Nancy 1 - FRANCE
--          Dominique COLNET and Suzanne COLLIN - SmartEiffel@loria.fr
--                       http://SmartEiffel.loria.fr
--
deferred class LARGE_INTEGER
--
-- To implement NUMBER (do not use this class, see NUMBER).
--

inherit ABSTRACT_INTEGER

feature

   is_zero: BOOLEAN is false

   is_one: BOOLEAN is false

   is_equal(other: NUMBER): BOOLEAN is
	 -- Compares two LARGE_INTEGERs. As they both have same sign
	 -- comparison is done with absolute values.
      require
	 other /= Void
      local
	 i: INTEGER; n2: like Current
      do
	 n2 ?= other
	 if n2 /= Void then
	    from
	       i := value.upper
	       Result := i = n2.value.upper
	    until
	       not Result or else i < 0
	    loop
	       Result := value.item(i) = n2.value.item(i)
	       i := i - 1
	    end
	 end
      end

feature{NUMBER}

   append_in(str:STRING) is
      local
	 i:INTEGER
	 s: STRING
      do
	 if is_negative then
	    str.extend('-')
	 end
	 str.append(storage.item(storage.upper).to_string)
	 from
	    i := storage.upper
	 until
	    i = storage.lower
	 loop
	    i := i - 1
	    s := storage.item(i).to_string
	    str.extend_multiple('0', (Base.log10.truncated_to_integer - s.count))
	    str.append(storage.item(i).to_string)
	 end
      end

   value: FIXED_ARRAY[INTEGER] is
      do
	 Result := storage
      end


   make_from_fixed_array(fa: FIXED_ARRAY[INTEGER]) is
      require
	 fa /= Void
      do
	 check
	    correct_fixed(fa)
	 end
	 storage := fa
      end


   make_smaller(int: INTEGER) is
      -- Creation of a large_integer with a too important integer
      do
	 !!storage.make(2)
	 storage.put((int \\ Base).abs,0)
	 storage.put((int // Base).abs,1)
      end

   make_from_large_product(int, other: INTEGER) is
      -- Creation of a large_integer with the multiplication of 2 integer
      do
	 temp_2_digints.put((other \\ Base).abs, 0)
	 temp_2_digints.put((other // Base).abs, 1)
	 storage := mult_fixed_with_integer(temp_2_digints,int.abs)
      end


   make_from_product(int, other: INTEGER) is
      local
	 v11, v12, v13, v21, v22, v23: INTEGER
	 ret: INTEGER
	 d1, d2, d3: INTEGER
      do
	 !!storage.make(2)
	 d1 := int.abs
	 d2 := other.abs
	 v11 := d1 // (Half_base_2)
	 v13 := d1 \\ (Half_base_2)
	 v12 := v13 // Half_base
	 v13 := v13 \\ Half_base
	 v21 := d2 // (Half_base_2)
	 v23 := d2 \\ (Half_base_2)
	 v22 := v23 // Half_base
	 v23 := v23 \\ Half_base

	 if Base_is_impair then
	    d1 :=v23 * v12 + v13 * v22
	    d2 := d1 // Half_base
	    d1 := (d1 - (d2 * Half_base)) * Half_base + v23 * v13
	    if d1 >= 2 * Half_base_2 then
	       d1 := d1 - (2 * (Half_base_2))
	       ret := 2
	    else
	       if d1 >= Half_base_2 then
		  d1 := d1 - (Half_base_2)
		  ret := 1
	       else
		  ret := 0
	       end
	    end
	    d2 := ret + d2 + (v23 * v11) + (v13 * v21) + (v12 * v22) + ((v11 * v22) \\ Half_base) * Half_base + ((v21 * v12) \\ Half_base) * Half_base
	    d3 := (v11 * v22) // Half_base + (v21 * v12) // Half_base + v11 * v21
	    ret := d2 // Rest_base
	    storage.put(d1 + (d2 - (ret * Rest_base)) * (Half_base_2), 0)
	    storage.put(d3 * (Half_base_2 // Rest_base) + ret, 1)
	 else
	    ret := v13 * v23
	    v11 := v12 * v23
	    v21 := v22 * v13
	    d1 := ret // Half_base + v11 \\ Half_base + v21 \\ Half_base
	    d2 := d1 \\ Half_base
	    storage.put((d1 - (d2 * Half_base)) * Half_base + ret \\ Half_base, 0)
	    storage.put(d2 + v11 // Half_base + v21 // Half_base + (v12 * v22), 1)
	 end
      end

   make_big is
      do
	 !!storage.make(3)
	 storage.put(1, 2)
      end


feature{NONE}

   create_positive(fa: FIXED_ARRAY[INTEGER]): ABSTRACT_INTEGER is
	 -- creates a simplified positive ABSTRACT_INTEGER
	 -- from a correct FIXED_ARRAY or a one item FIXED
      require
	 fa /= Void
	 internal_correct_fixed(fa)
      do
	 if (fa.upper > 0) then
	    !LARGE_POSITIVE_INTEGER!Result.make_from_fixed_array(clone(fa))
	 elseif (fa.upper = 0) then
	    !SMALL_INTEGER!Result.make(fa.item(0))
	 else
	    Result ?= zero
	 end
      ensure
	 Result /= Void
	 Result.is_abstract_integer
      end

   create_negative(fa: FIXED_ARRAY[INTEGER]): ABSTRACT_INTEGER is
	 -- creates a simplified negative ABSTRACT_INTEGER
	 -- from a correct FIXED_ARRAY or a one item FIXED
      require
	 fa /= Void
	 internal_correct_fixed(fa)
      do
	 if fa.upper > 0 then
	    !LARGE_NEGATIVE_INTEGER!Result.make_from_fixed_array(clone(fa))
	 elseif fa.upper = 0 then
	    !SMALL_INTEGER!Result.make(- (fa.item(0)))
	 else
	    Result ?= zero
	 end
      ensure
	 Result /= Void
	 Result.is_abstract_integer
      end

   create_positive_directly(fa: FIXED_ARRAY[INTEGER]): ABSTRACT_INTEGER is
	 -- creates a simplified positive ABSTRACT_INTEGER
	 -- from a correct FIXED_ARRAY or a one item FIXED
      require
	 fa /= Void
	 internal_correct_fixed(fa)
      do
	 if (fa.upper > 0) then
	    !LARGE_POSITIVE_INTEGER!Result.make_from_fixed_array(fa)
	 elseif (fa.upper = 0) then
	    !SMALL_INTEGER!Result.make(fa.item(0))
	 else
	    Result ?= zero
	 end
      ensure
	 Result /= Void
	 Result.is_abstract_integer
      end

   create_negative_directly(fa: FIXED_ARRAY[INTEGER]): ABSTRACT_INTEGER is
	 -- creates a simplified negative ABSTRACT_INTEGER
	 -- from a correct FIXED_ARRAY or a one item FIXED
      require
	 fa /= Void
	 internal_correct_fixed(fa)
      do
	 if fa.upper > 0 then
	    !LARGE_NEGATIVE_INTEGER!Result.make_from_fixed_array(fa)
	 elseif fa.upper = 0 then
	    !SMALL_INTEGER!Result.make(- (fa.item(0)))
	 else
	    Result ?= zero
	 end
      ensure
	 Result /= Void
	 Result.is_abstract_integer
      end

feature {NONE} -- Conversion tool

   fixed_array_to_double(fa: FIXED_ARRAY[INTEGER]): DOUBLE is
	 -- only a tool
	 -- unsigned conversion
      require
	 fa /= Void
	 correct_fixed(fa)
      local
	 i : INTEGER
      do
	 from
	    i := fa.upper - 1
	    Result := fa.item(fa.upper).to_double
	 until
	    (i < 0) or else (Result > Maximum_double)
	 loop
	    Result := (Result * Double_base) + fa.item(i).to_double
	    i := i - 1
	 end
	 if (Result = Maximum_double) and then (fa.item(0) /= 0) then
	    Result := Maximum_double * 2
	 end
      end


feature{NONE} -- Operations tools

      add_fixed_array_with_integer_in_himself_from(fa1: INTEGER; fa2: FIXED_ARRAY[INTEGER]; n: INTEGER) is
	 -- only a tool used by some features in positive
	 -- and negative large integers
	 -- result is stored in fa2
	 -- Make the addition between fa2 and fa1 which is shifted by
	 -- n and return the result in fa2 to have a
	 -- good memory gestion.
      require
	 fa2 /= Void
      local
	 i, carry, partial_sum,
	 initial_larger_upper: INTEGER
      do
	 initial_larger_upper := fa2.upper
	 partial_sum := fa2.item(n) + fa1
	 if partial_sum >= Base or else partial_sum < 0 then
	    carry := 1
	    fa2.put(partial_sum - Base, n)
	 else
	    carry := 0
	    fa2.put(partial_sum, n)
	 end
	 from
	    i := n + 1
	 until
	    (i > initial_larger_upper)
	 loop
	    partial_sum := fa2.item(i) + carry
	    if partial_sum >= Base or else partial_sum < 0 then
	       carry := 1
	       fa2.put(partial_sum - Base, i)
	    else
	       carry := 0
	       fa2.put(partial_sum, i)
	    end
	    i := i + 1
	 end
	 if (carry /= 0) then
	    fa2.add_last(carry)
	 end
      ensure
	 fa2.item(fa2.upper) /= 0
      end

   add_fixed_arrays(fa1, fa2: FIXED_ARRAY[INTEGER]): FIXED_ARRAY[INTEGER] is
	 -- only a tool used by some features in positive
	 -- and negative large integers
	 -- Give a FIXED_ARRAY[INTEGER] for the creation of an
	 -- large_integer after an addition.
      require
	 fa1 /= Void
	 fa2 /= Void
      local
	 smaller, larger: FIXED_ARRAY[INTEGER]
	 i, carry, partial_sum,
	 initial_smaller_upper, initial_larger_upper: INTEGER
      do
	 if fa1.upper >= fa2.upper then
	    smaller := fa2
	    larger := fa1
	 else
	    smaller := fa1
	    larger := fa2
	 end
	 from
	    initial_smaller_upper := smaller.upper
	    initial_larger_upper := larger.upper
	    !!Result.make(larger.count + 1)
	    i := 0
	    carry := 0
	 until
	    i > initial_smaller_upper
	 loop
            partial_sum := larger.item(i) + smaller.item(i) + carry
            if partial_sum >= Base or else partial_sum < 0 then
               carry := 1
               Result.put(partial_sum - Base, i)
            else
               carry := 0
               Result.put(partial_sum, i)
            end
	    i := i + 1
	 end
	 from
	 until
	    (i > initial_larger_upper)
	 loop
            partial_sum := larger.item(i) + carry
            if partial_sum >= Base or else partial_sum < 0 then
               carry := 1
               Result.put(partial_sum - Base, i)
            else
               carry := 0
               Result.put(partial_sum, i)
            end
	    i := i + 1
	 end
	 if (carry = 0) then
	    Result.remove_last
	 else
	    Result.put(carry,i)
	 end
      ensure
	 Result.item(Result.upper) /= 0
      end

      add_fixed_arrays_in_himself(fa1, fa2: FIXED_ARRAY[INTEGER]) is
	 -- only a tool used by some features in positive
	 -- and negative large integers
	 -- result is stored in fa2
	 -- Make the addition and return the result in fa2 to have a
	 -- good memory gestion.
      require
	 fa1 /= Void
	 fa2 /= Void
      local
	 smaller, larger: FIXED_ARRAY[INTEGER]
	 i, carry, partial_sum,
	 initial_smaller_upper, initial_larger_upper: INTEGER
      do
	 if fa1.upper >= fa2.upper then
	    smaller := fa2
	    larger := fa1
	 else
	    smaller := fa1
	    larger := fa2
	 end
	 from
	    initial_smaller_upper := smaller.upper
	    initial_larger_upper := larger.upper
	    i := 0
	    carry := 0
	 until
	    i > initial_smaller_upper
	 loop
            partial_sum := larger.item(i) + smaller.item(i) + carry
            if partial_sum >= Base or else partial_sum < 0 then
               carry := 1
               fa2.put(partial_sum - Base, i)
            else
               carry := 0
               fa2.put(partial_sum, i)
            end
	    i := i + 1
	 end
	 from
	 until
	    (i > initial_larger_upper)
	 loop
            partial_sum := larger.item(i) + carry
            if partial_sum >= Base or else partial_sum < 0 then
               carry := 1
               fa2.put(partial_sum - Base, i)
            else
               carry := 0
               fa2.put(partial_sum, i)
            end
	    i := i + 1
	 end
	 if (carry /= 0) then
	    fa2.add_last(carry)
	 end
      ensure
	 fa2.item(fa2.upper) /= 0
      end

      add_fixed_arrays_in_himself_from(fa1, fa2: FIXED_ARRAY[INTEGER]; n: INTEGER) is
	 -- only a tool used by some features in positive
	 -- and negative large integers
	 -- result is stored in fa2
	 -- Make the addition between fa2 and fa1 which is shifted by
	 -- n and return the result in fa2 to have a
	 -- good memory gestion.
      require
	 fa1 /= Void
	 fa2 /= Void
      local
	 i, carry, partial_sum,
	 initial_smaller_upper, initial_larger_upper: INTEGER
      do
	 from
	    initial_smaller_upper := fa1.upper + n
	    initial_larger_upper := fa2.upper
	    i := n
	    carry := 0
	 until
	    i > initial_smaller_upper
	 loop
	    partial_sum := fa2.item(i) + fa1.item(i - n) + carry
	    if partial_sum >= Base or else partial_sum < 0 then
	       carry := 1
	       fa2.put(partial_sum - Base, i)
	    else
	       carry := 0
	       fa2.put(partial_sum, i)
	    end
	    i := i + 1
	 end
	 from
	 until
	    (i > initial_larger_upper)
	 loop
	    partial_sum := fa2.item(i) + carry
	    if partial_sum >= Base or else partial_sum < 0 then
	       carry := 1
	       fa2.put(partial_sum - Base, i)
	    else
	       carry := 0
	       fa2.put(partial_sum, i)
	    end
	    i := i + 1
	 end
	 if (carry /= 0) then
	    fa2.add_last(carry)
	 end
      ensure
	 fa2.item(fa2.upper) /= 0
      end

   difference_between_fixed_arrays(larger, smaller: FIXED_ARRAY[INTEGER]):FIXED_ARRAY[INTEGER] is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- Give a FIXED_ARRAY[INTEGER] for the creation of an
	 -- large_integer after an subtraction.
      require
	 smaller /= Void
	 larger /= Void
	 not fixed_array_greater_than(smaller, larger) -- smaller <= larger
      local
	 i, last_not_zero, carry, partial_sum, larger_upper, smaller_upper: INTEGER
      do
	 from
	    larger_upper := larger.upper
	    smaller_upper := smaller.upper
	    i := 0
	    !!Result.make(larger.count)
	    carry := 0
	    last_not_zero := -1
	 until
	    i > smaller_upper
	 loop
	    partial_sum := larger.item(i) - smaller.item(i) - carry
	    if (partial_sum < 0) then
	       carry := 1
	       Result.put(partial_sum + Base , i)
	       if (partial_sum + Base ) /= 0 then
		  last_not_zero := i
	       end
	    else
	       carry := 0
	       Result.put(partial_sum, i)
	       if partial_sum /= 0 then
		  last_not_zero := i
	       end
	    end
	    i := i + 1
	 end
	 from
	 until
	    (i > larger_upper)
	 loop
	    partial_sum := larger.item(i) - carry
	    if (partial_sum < 0) then
	       carry := 1
	       Result.put(partial_sum + Base , i)
	       if (partial_sum + Base ) /= 0 then
		  last_not_zero := i
	       end
	    else
	       carry := 0
	       Result.put(partial_sum, i)
	       if partial_sum /= 0 then
		  last_not_zero := i
	       end
	    end
	    i := i + 1
	 end
	 Result.resize(last_not_zero + 1)
      ensure
	  internal_correct_fixed(Result)
      end

   difference_between_fixed_arrays_in_himself(larger, smaller: FIXED_ARRAY[INTEGER]) is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- result is stored in larger
	 -- Make the subtraction and return the result in larger to have a
	 -- good memory gestion.
	 -- Use this function if you know that larger is greater than
	 -- smaller.
      require
	 smaller /= Void
	 larger /= Void
	 not fixed_array_greater_than(smaller, larger) -- smaller <= larger
      local
	 i, last_not_zero, carry, partial_sum, larger_upper,smaller_upper: INTEGER
      do
	 from
	    larger_upper := larger.upper
	    smaller_upper := smaller.upper
	    i := 0
	    carry := 0
	    last_not_zero := -1
	 until
	    i > smaller_upper
	 loop
	    partial_sum := larger.item(i) - smaller.item(i) - carry
	    if (partial_sum < 0) then
	       carry := 1
	       larger.put(partial_sum + Base , i)
	       if (partial_sum + Base ) /= 0 then
		  last_not_zero := i
	       end
	    else
	       carry := 0
	       larger.put(partial_sum, i)
	       if partial_sum /= 0 then
		  last_not_zero := i
	       end
	    end
	    i := i + 1
	 end
	 from
	 until
	    (i > larger_upper)
	 loop
	    partial_sum := larger.item(i) - carry
	    if (partial_sum < 0) then
	       carry := 1
	       larger.put(partial_sum + Base , i)
	       if (partial_sum + Base ) /= 0 then
		  last_not_zero := i
	       end
	    else
	       carry := 0
	       larger.put(partial_sum, i)
	       if partial_sum /= 0 then
		  last_not_zero := i
	       end
	    end
	    i := i + 1
	 end
	 larger.resize(last_not_zero + 1)
      ensure
	 internal_correct_fixed(larger)
      end

   difference_between_fixed_arrays_in_himself_from(larger, smaller: FIXED_ARRAY[INTEGER]; n: INTEGER) is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- result is stored in larger
	 -- Make the subtraction between larger and smaller which is
	 -- shifted by n and return the result in larger to have a
	 -- good memory gestion.
	 -- Use this function if you know that larger is greater than
	 -- smaller.
      require
	 smaller /= Void
	 larger /= Void
	 not fixed_array_greater_than(smaller, larger) -- smaller <= larger
      local
	 a, i, last_not_zero, carry, partial_sum, larger_upper,smaller_upper: INTEGER
      do
	 from
	    larger_upper := larger.upper
	    smaller_upper := smaller.upper
	    i := n
	    a := 0
	    carry := 0
	    last_not_zero := n - 1
	 until
	    a > smaller_upper
	 loop
	    partial_sum := larger.item(i) - smaller.item(a) - carry
	    if (partial_sum < 0) then
	       carry := 1
	       larger.put(partial_sum + Base , i)
	       if (partial_sum + Base ) /= 0 then
		  last_not_zero := i
	       end
	    else
	       carry := 0
	       larger.put(partial_sum, i)
	       if partial_sum /= 0 then
		  last_not_zero := i
	       end
	    end
	    i := i + 1
	    a := a + 1
	 end
	 from
	 until
	    (i > larger_upper)
	 loop
	    partial_sum := larger.item(i) - carry
	    if (partial_sum < 0) then
	       carry := 1
	       larger.put(partial_sum + Base , i)
	       if (partial_sum + Base ) /= 0 then
		  last_not_zero := i
	       end
	    else
	       carry := 0
	       larger.put(partial_sum, i)
	       if partial_sum /= 0 then
		  last_not_zero := i
	       end
	    end
	    i := i + 1
	 end
	 larger.resize(last_not_zero + 1)
      ensure
	 internal_correct_fixed(larger)
      end

   mult_fixed_with_integer(fa: FIXED_ARRAY[INTEGER]; int: INTEGER): FIXED_ARRAY[INTEGER] is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- Give a FIXED_ARRAY[INTEGER] for the creation of an
	 -- large_integer after an multiplication between a
	 -- large_integer and a small_integer.
      require
	 fa /= Void
	 int /= 0
      local
	 v11, v12, v13, v21, v22, v23: INTEGER
	 ret, retenue: INTEGER
	 d1, d2, d3: INTEGER
	 i, bsup : INTEGER
      do
	 !!Result.make(((nb_c(fa.item(fa.upper)) + 9 * (fa.count - 1) + nb_c(int)) / 9).ceiling)
	 from
	    v11 := int // (Half_base_2)
	    v13 := int \\ (Half_base_2)
	    v12 := v13 // Half_base
	    v13 := v13 \\ Half_base
	    i := Result.lower - 1
	    retenue := 0
	    bsup := fa.upper
	 until
	    i = Result.upper
	 loop
	    i := i + 1
	    if (i <= bsup) then
	       v21 := fa.item(i) // (Half_base_2)
	       v23 := fa.item(i) \\ (Half_base_2)
	       v22 := v23 // Half_base
	       v23 := v23 \\ Half_base
	       if Rest_base = 10 then
		  d1 := v23 * v12 + v13 * v22
		  d2 := d1 // Half_base
		  d1 := (d1 - (d2 * Half_base)) * Half_base + v23 * v13
		  if d1 >= 2 * Half_base_2 then
		     d1 := d1 - (2 * (Half_base_2))
		     ret := 2
		  else
		     if d1 >= Half_base_2 then
			d1 := d1 - (Half_base_2)
			ret := 1
		     else
			ret := 0
		     end
		  end
		  d2 := ret + d2 + (v23 * v11) + (v13 * v21) + (v12 * v22) + ((v11 * v22) \\ Half_base) * Half_base + ((v21 * v12) \\ Half_base) * Half_base
		  d3 := (v11 * v22) // Half_base + (v21 * v12) // Half_base + v11 * v21
		  ret := d2 // Rest_base
		  d1 := d1 + (d2 - (ret * Rest_base)) * (Half_base_2)
		  d2 := d3 * (Half_base_2 // Rest_base) + ret
	       else
		  ret := v13 * v23
		  v11 := v12 * v23
		  v21 := v22 * v13
		  d1 := ret // Half_base + v11 \\ Half_base + v21 \\ Half_base
		  d2 := d1 \\ Half_base
		  d1 := (d1 - (d2 * Half_base)) * Half_base + ret \\ Half_base
		  d2 := d2 + v11 // Half_base + v21 // Half_base + (v12 * v22)
	       end
	       d3 := d1 + retenue
	       if d3 >= Base or else d3 < 0 then
		  retenue := d2 + 1
		  Result.put(d3 - Base, i)
	       else
		  retenue := d2
		  Result.put(d3, i)
	       end
	    else
	       if retenue >= Base or else retenue < 0 then
		  Result.put(retenue - Base, i)
	       else
		  Result.put(retenue, i)
	       end
	    end
	 end
	 if Result.item(Result.upper) = 0 then
	    Result.remove_last
	 end
      ensure
	 internal_correct_fixed(Result)
      end

   mult_fixed_with_integer_in_temp(fa: FIXED_ARRAY[INTEGER]; int: INTEGER) is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- Give a FIXED_ARRAY[INTEGER] for the creation of an
	 -- large_integer after an multiplication between a
	 -- large_integer and a small_integer.
      require
	 fa /= Void
	 int /= 0
      local
	 v11, v12, v13, v21, v22, v23: INTEGER
	 ret, retenue: INTEGER
	 d1, d2, d3: INTEGER
	 i, bsup : INTEGER
      do
	 temp_after_mult.resize(((nb_c(fa.item(fa.upper)) + nb_c(int) + 9 * (fa.count - 1)) / 9).ceiling)
	 from
	    v11 := int // (Half_base_2)
	    v13 := int \\ (Half_base_2)
	    v12 := v13 // Half_base
	    v13 := v13 \\ Half_base
	    i := temp_after_mult.lower - 1
	    retenue := 0
	    bsup := fa.upper
	 until
	    i = temp_after_mult.upper
	 loop
	    i := i + 1
	    if (i <= bsup) then
	       v21 := fa.item(i) // (Half_base_2)
	       v23 := fa.item(i) \\ (Half_base_2)
	       v22 := v23 // Half_base
	       v23 := v23 \\ Half_base
	       if Rest_base = 10 then
		  d1 := v23 * v12 + v13 * v22
		  d2 := d1 // Half_base
		  d1 := (d1 - (d2 * Half_base)) * Half_base + v23 * v13
		  if d1 >= 2 * Half_base_2 then
		     d1 := d1 - (2 * (Half_base_2))
		     ret := 2
		  else
		     if d1 >= Half_base_2 then
			d1 := d1 - (Half_base_2)
			ret := 1
		     else
			ret := 0
		     end
		  end
		  d2 := ret + d2 + (v23 * v11) + (v13 * v21) + (v12 * v22) + ((v11 * v22) \\ Half_base) * Half_base + ((v21 * v12) \\ Half_base) * Half_base
		  d3 := (v11 * v22) // Half_base + (v21 * v12) // Half_base + v11 * v21
		  ret := d2 // Rest_base
		  d1 := d1 + (d2 - (ret * Rest_base)) * (Half_base_2)
		  d2 := d3 * (Half_base_2 // Rest_base) + ret
	       else
		  ret := v13 * v23
		  v11 := v12 * v23
		  v21 := v22 * v13
		  d1 := ret // Half_base + v11 \\ Half_base + v21 \\ Half_base
		  d2 := d1 \\ Half_base
		  d1 := (d1 - (d2 * Half_base)) * Half_base + ret \\ Half_base
		  d2 := d2 + v11 // Half_base + v21 // Half_base + (v12 * v22)
	       end
	       d3 := d1 + retenue
	       if d3 >= Base or else d3 < 0 then
		  retenue := d2 + 1
		  temp_after_mult.put(d3 - Base, i)
	       else
		  retenue := d2
		  temp_after_mult.put(d3, i)
	       end
	    else
	       if retenue >= Base or else retenue < 0 then
		  temp_after_mult.put(retenue - Base, i)
	       else
		  temp_after_mult.put(retenue, i)
	       end
	    end
	 end
	 if temp_after_mult.item(temp_after_mult.upper) = 0 then
	    temp_after_mult.remove_last
	 end
      ensure
	 internal_correct_fixed(temp_after_mult)
      end

   mult_fixed_with_integer_in(fa1: FIXED_ARRAY[INTEGER]; int: INTEGER; fa2: FIXED_ARRAY[INTEGER]) is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- result is stored in fa2
	 -- Make after the multiplication between a large_integer and
	 -- a small_integer i shift and return the result in fa2 to have a
	 -- good memory gestion.
	 -- Use this function if you know that larger is greater than
	 -- smaller.
      require
	 fa1 /= Void
	 fa2 /= Void
	 int > 0
      local
	 v11, v12, v13, v21, v22, v23: INTEGER
	 ret, retenue: INTEGER
	 d1, d2, d3: INTEGER
	 i, bsup : INTEGER
      do
	 fa2.resize(((fa1.item(fa1.upper).log10.truncated_to_integer + int.log10.truncated_to_integer + 9 * (fa1.count - 1) + 2) / 9).ceiling)
	 from
	    v11 := int // (Half_base_2)
	    v13 := int \\ (Half_base_2)
	    v12 := v13 // Half_base
	    v13 := v13 \\ Half_base
	    i := fa2.lower - 1
	    retenue := 0
	    bsup := fa1.upper
	 until
	    i = fa2.upper
	 loop
	    i := i + 1
	    if (i <= bsup) then
	       v21 := fa1.item(i) // (Half_base_2)
	       v23 := fa1.item(i) \\ (Half_base_2)
	       v22 := v23 // Half_base
	       v23 := v23 \\ Half_base

	       if Rest_base = 10 then
		  d1 := v23 * v12 + v13 * v22
		  d2 := d1 // Half_base
		  d1 := (d1 - (d2 * Half_base)) * Half_base + v23 * v13
		  if d1 >= 2 * Half_base_2 then
		     d1 := d1 - (2 * (Half_base_2))
		     ret := 2
		  else
		     if d1 >= Half_base_2 then
			d1 := d1 - Half_base_2
			ret := 1
		     else
			ret := 0
		     end
		  end
		  d2 := ret + d2 + (v23 * v11) + (v13 * v21) + (v12 * v22) + ((v11 * v22) \\ Half_base) * Half_base + ((v21 * v12) \\ Half_base) * Half_base
		  d3 := (v11 * v22) // Half_base + (v21 * v12) // Half_base + v11 * v21
		  ret := d2 // Rest_base
		  d1 := d1 + (d2 - (ret * Rest_base)) * (Half_base_2)
		  d2 := d3 * (Half_base_2 // Rest_base) + ret
	       else
		  ret := v13 * v23
		  v11 := v12 * v23
		  v21 := v22 * v13
		  d1 := ret // Half_base + v11 \\ Half_base + v21 \\ Half_base
		  d2 := d1 \\ Half_base
		  d1 := (d1 - (d2 * Half_base)) * Half_base + ret \\ Half_base
		  d2 := d2 + v11 // Half_base + v21 // Half_base + (v12 * v22)
	       end
	       d3 := d1 + retenue
	       if d3 >= Base or else d3 < 0 then
		  retenue := d2 + 1
		  fa2.put(d3 - Base, i)
	       else
		  retenue := d2
		  fa2.put(d3, i)
	       end
	    else
	       if retenue >= Base or else retenue < 0 then
		  fa2.put(retenue - Base, i)
	       else
		  fa2.put(retenue, i)
	       end
	    end
	 end
	 if fa2.item(fa2.upper) = 0 then
	    fa2.remove_last
	 end
      ensure
	 internal_correct_fixed(fa2)
      end

   mult_2_fixed(fa1, fa2: FIXED_ARRAY[INTEGER]): FIXED_ARRAY[INTEGER] is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- Give a FIXED_ARRAY[INTEGER] for the creation of an
	 -- large_integer after the multiplication of 2 large_integer.
      require
	 fa1 /= Void
	 fa2 /= Void
      local
	 i : INTEGER
      do
	 !!Result.make(((fa1.item(fa1.upper).log10.truncated_to_integer + 9 * (fa1.count - 1) + fa2.item(fa2.upper).log10.truncated_to_integer + 9 * (fa2.count - 1) + 2) / 9).ceiling)
	 from
	    mult_fixed_with_integer_in(fa1, fa2.item(fa2.upper), Result)
	    i := fa2.upper - 1
	 until
	    i < 0
	 loop
	    shift(Result)
	    if (fa2.item(i) /= 0) then
	       mult_fixed_with_integer_in(fa1, fa2.item(i), temp_from_mult)
	       add_fixed_arrays_in_himself(temp_from_mult, Result)
	    end
	    i := i - 1
	 end
      ensure
	  internal_correct_fixed(Result)
      end

   mult_2_fixed_in_temp(fa1, fa2: FIXED_ARRAY[INTEGER]) is
	 -- only a tool used by some features in positive and negative
	 -- large integers
	 -- Warning : temp can be an empty array if result is zero
	 -- Result is stored in temp_after_mult
	 -- Make the multiplication between 2 large_integer and the
	 -- result is stored in tmp_from_div to have a good memory gestion
      require
	 fa1 /= Void
	 fa2 /= Void
      local
	 i : INTEGER
      do
	 from
	    mult_fixed_with_integer_in(fa1, fa2.item(fa2.upper), temp_after_mult)
	    i := fa2.upper - 1
	 until
	    i < 0
	 loop
	    shift(temp_after_mult)
	    if (fa2.item(i) /= 0) then
	       mult_fixed_with_integer_in(fa1, fa2.item(i), temp_from_mult)
	       add_fixed_arrays_in_himself(temp_from_mult, temp_after_mult)
	    end
	    i := i - 1
	 end
      ensure
	  internal_correct_fixed(temp_after_mult)
      end

   -- constants for integer division

   fa_one: FIXED_ARRAY[INTEGER] is
      once
	 !!Result.make(0)
	 Result.add_last(1)
      ensure
	 Result /= Void and then (Result.item(0) = 1)
      end

   divise_fixed_array(dividende, divisor : FIXED_ARRAY[INTEGER]) is
	 -- quotient is stored in temp_quotient, remainder in temp_remainder
	 -- Make the division between 2 abstract_integer.
	 -- quotient is stored in temp_quotient.
	 -- remainder is stored in temp_remainder.
      require
	 dividende /= Void
	 internal_correct_fixed(dividende)
	 divisor /= Void
	 internal_correct_fixed(divisor)
	 divisor.upper >= 0
      local
	 double_num, double_den, approx : DOUBLE
	 n, val: INTEGER
	 t, td: BOOLEAN
      do
	 if fixed_array_greater_than(divisor, dividende) then
	    temp_quotient.resize(0)
	    temp_remainder.copy(dividende)
	 elseif dividende.is_equal(divisor) then
	    temp_quotient.copy(fa_one)
	    temp_remainder.resize(0)
	 else
	    from
	       temp_remainder.copy(dividende)
	       temp_quotient.resize(0)
	       t := true
	    until
	       (temp_remainder.upper < 0)
		  or else fixed_array_greater_than(divisor, temp_remainder)
	    loop
	       n := temp_remainder.upper - divisor.upper
	       if (n = 0) then
		  double_num := temp_remainder.item(temp_remainder.upper)
		  double_den := divisor.item(divisor.upper)
		  if (divisor.upper > 0) then
		     double_num := (double_num * Double_base)
			+ temp_remainder.item(temp_remainder.upper - 1)
		     double_den := (double_den * Double_base)
			+ divisor.item(divisor.upper - 1)
		  end
	       else
		  double_num := temp_remainder.item(temp_remainder.upper)
		  double_num := (double_num * Double_base)
		     + temp_remainder.item(temp_remainder.upper - 1)
		  double_den := divisor.item(divisor.upper)
		  n := n - 1
	       end
	       approx := double_num / (double_den + 1)
	       if approx < 1 then
		  approx := 1.01
	       end
	       if (approx >= Double_base) then
		  temp_2_digints.put((approx / Double_base).truncated_to_integer, 1)
		  temp_2_digints.put((approx - (Double_base * temp_2_digints.item(1))).truncated_to_integer, 0)
		  td := false
		  if t then
		     t := false
		     temp_quotient.resize(2 + n)
		  end
	       else
		  val := approx.truncated_to_integer
		  td := true
		  if t then
		     t := false
		     temp_quotient.resize(1 + n)
		  end
	       end
	       if td then
		  add_fixed_array_with_integer_in_himself_from(val, temp_quotient, n)
		  mult_fixed_with_integer_in_temp(divisor, val)
	       else
		  add_fixed_arrays_in_himself_from(temp_2_digints, temp_quotient, n)
		  mult_2_fixed_in_temp(temp_2_digints, divisor)
	       end
	       difference_between_fixed_arrays_in_himself_from(temp_remainder, temp_after_mult, n)
	    end
	 end
      ensure
	 internal_correct_fixed(temp_remainder)
	 internal_correct_fixed(temp_quotient)
      end

   shift(fa: FIXED_ARRAY[INTEGER]) is
      require
	 fa /= Void
      local
	 i : INTEGER
      do
	 from
	    i := fa.upper
	    fa.resize(fa.upper + 2)
	 until
	    i < 0
	 loop
	    fa.put(fa.item(i), i + 1)
	    i := i - 1
	 end
	 fa.put(0,0)
      end

feature {NONE} -- Comparison tools

   fixed_array_greater_than(fa1, fa2: FIXED_ARRAY[INTEGER]): BOOLEAN is
      require
	 fa1 /= Void
	 internal_correct_fixed(fa1)
	 fa2 /= Void
	 internal_correct_fixed(fa2)
      local
	 i : INTEGER
      do
	 if (fa1.upper = fa2.upper) then
	    from
	       i := fa1.upper
	    until
	       (i < 0) or else ( (fa1 @ i) /= (fa2 @ i) )
	    loop
	       i := i - 1
	    end
	    Result := (i >= 0) and then ((fa1 @ i) > (fa2 @ i))
	 else
	    Result := fa1.upper > fa2.upper
	 end
      end


feature{NUMBER} -- validity check

   internal_correct_fixed(fa: FIXED_ARRAY[INTEGER]): BOOLEAN is
      do
	 Result := correct_fixed(fa)
		    or else ((fa.upper = 0) and then (fa.item(0) /= 0))
		    or else (fa.upper = -1)
      end

   correct_fixed(fa: FIXED_ARRAY[INTEGER]): BOOLEAN is
      local
	 i : INTEGER
      do
	 from
	    i := fa.upper
	    Result := ((fa.upper >= 1) and then (fa.item(fa.upper) /= 0 ))
	 until
	    (i < 0) or else (not Result)
	 loop
	    Result := (fa.item(i) >= 0)
	    i := i - 1
	 end
      end

feature {NONE}

   storage : FIXED_ARRAY[INTEGER]

   view: STRING is
	 -- for debugging only
	 -- print storage contents
      local
	 i : INTEGER
      do
	 !!Result.make(0) 
	 from
	    i := storage.lower
	 variant
	    storage.upper - i
	 until
	    i > storage.upper
	 loop
	    Result.append( i.to_string ) 
	    Result.append( once " -> " ) 
	    Result.append( storage.item(i).to_string ) 
	    Result.append_character('%N') 
	    i := i + 1 
	 end
      end

invariant

   correct_fixed(storage)

end -- LARGE_INTEGER