Integer size and Unbounded_Integer size (aka: determine the length of a digit string)

General
1

Hi;

I have another dumb question.

Integer size and Unbounded_Integer size (aka: determine the length of a digit string)

I : Integer := 12345;

By visual inspection, the length of the digit string is 5.

I could use base 10 log to derive the length of the digit string…

But how to do it without using base 10 log?

The Length function won’t handle an integer…

Length of the Image of the Integer?

What String type do I need? Unbounded? Mix of Unbounded and Fixed?

Real simple using AWK or Perl: length (digit_string)…

But I want to use a ““Real”” Language :slight_smile:

I’ve reviewed (again) the Learn pages by AdaCore (strings and arrays), and I’m just not able to extract the meaningful bits to answer my own question.

Now, how to do this with an Unbounded_Integer (Jeff?)

I’m trying to solve the Rosetta Code “Left factorials” Task using Ada.

GNAT.Big_Integers fails (overflows) on the last set of steps (but I don’t know how to get the length of the digit string anyway).

So I’m using PragmARC. So, I can calculate all of the left factorials that are requested (Yay!), but I don’t know how to return the length of those huge integers.

Sorry for such a dumb question, as I’m sure the answer is right under my nose, but I just don’t see it.

Thanks,
RBE

2

It appears that what you want is the number of digits in the decimal representation of the value. I’d do

Value  : PragmARC.Unbounded_Numbers.Integers.Unbounded_Integer;
Length : Positive;
...
Length := PragmARC.Unbounded_Numbers.Integers.Image (Value)'Length;
1 Like
3

You cannot avoid logarithm. Whatever method you would use it would be an equivalent of taking lg (X) and rounding it.

Here is a full solution with Simple Components:

with Ada.Calendar;           use Ada.Calendar;
with Ada.Text_IO;            use Ada.Text_IO;
with Unbounded_Unsigneds;    use Unbounded_Unsigneds;
with Strings_Edit.Integers;  use Strings_Edit.Integers;

with Strings_Edit.Unbounded_Unsigned_Edit;
use  Strings_Edit.Unbounded_Unsigned_Edit;

procedure Test is
   use Strings_Edit;

   function Left_Factorial (N : Natural) return Unbounded_Unsigned is
   begin
      if N = 0 then
         return Zero;
      else
         declare
            Factorial : Unbounded_Unsigned := One;
            Result    : Unbounded_Unsigned := One;
         begin
            for I in 1..N - 1 loop
               Mul (Factorial, Half_Word (I));
               Add (Result, Factorial);
            end loop;
            return Result;
         end;
      end if;
   end Left_Factorial;

   Line    : String (1..256);
   Pointer : Integer := 1;
begin
   Put_Line ("Zero to Ten:");
   for I in 0..10 loop
      if I /= 0 then
         Put (Line, Pointer, ", ");
      end if;
      Put (Line, Pointer, Left_Factorial (I));
   end loop;
   Put_Line (Line (1..Pointer - 1));
   Put_Line ("!20 to !110 by 10:");
   for I in 2..11 loop
      Pointer := 1;
      Put (Line, Pointer, Left_Factorial (I * 10));
      Put_Line (Line (1..Pointer - 1));
   end loop;
   Put_Line ("Decimal places counts !1000 to !10000 by 1000:");
      Pointer := 1;
   for I in 1..10 loop
      if I /= 1 then
         Put (Line, Pointer, ", ");
      end if;
      declare
         Value  : Unbounded_Unsigned := Left_Factorial (I * 1000);
         Length : Natural := 0;
      begin
         while not Is_Zero (Value) loop
            if Value >= 1_000_000 then
               Div (Value, 1_000_000);
               Length := Length + 6;
            else
               Div (Value, 10);
               Length := Length + 1;
            end if;
         end loop;
         Put (Line, Pointer, Length);
      end;
   end loop;
   Put_Line (Line (1..Pointer - 1));
end Test;

Here logarithm is computed by direct division, slightly optimized by dividing by 1_000_000 when possible. For very large numbers you would use other method by dividing by 10*2**K, which becomes a simple shift.

However, in practice, nobody does this stuff. Factorials and other huge functions are computed under some modulus, usually prime.

Output:

Zero to Ten:
0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114
!20 to !110 by 10:
128425485935180314
9157958657951075573395300940314
20935051082417771847631371547939998232420940314
620960027832821612639424806694551108812720525606160920420940314
141074930726669571000530822087000522211656242116439949000980378746128920420940314
173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
Decimal places counts !1000 to !10000 by 1000:
2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656
1 Like
4

Numerically?
IIRC, you use ln(10) / ln(2) to change-of-base.
If that route, then you probably want to use named numbers.

This is a good method to use, as it depends only on attributes, but if you do remember to account for the added space/-/+. (The image of your I would yield 12345, thus a length of 6.)

If you’re hardcoding, you can use analysis to get your maximum length; you can use this to make a subtype that encodes the properties, perhaps:

  -- Define the digits.
   subtype Digit        is Character range '0'..'9';
   -- Constrain our indices.
   subtype Digit_Index  is Positive  range  1 .. 5 ;
   -- Define a subtype conforming to our constraints.
   -- NOTE: This allows for length to be 0, this may or may not match your
   --       actual constraints, it the empty-string is disallowed, simply
   --       replace the IF-expression withthe THEN-clause.
   subtype Digit_String is String
      with Dynamic_Predicate =>
           (if Digit_String'Length in Positive then Digit_String'Length in Digit_Index) 
       and (for all Ch of Digit_String => Ch in Digit);
1 Like