Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2965

Integer sizes and DFAs

Show all headers | View raw

One of the posters mentioned that ignoring the size of integers used
in the DFAs was "not computer science". Actually, it is.  It's called
the RAM model of computing.  And, in it you assume each "integer"
occupies one location and is also sufficient to address any memory
location.  Sa, accessing any integer any where in memory is an O(1)
operation.

Note how that even works for the DNA DFAs, assuming 32 bit integers
and a byte addressed machine.  With that model, you can fit 10 million
(1E7) states in the 2 billion byte (2GB) address space (each state has
4, 4 byte entries or 16 bytes).  You might even fit something over 100
million (1E8) states there.  Thus, your memory access time is linear
in the worst case (assuming every request is a cache miss).

With 64 bit integers, one is essentially only limited by total memory
(including disk) and it is still linear although the worst case time
is every access is a page fault.  Probably not particularly practical,
but CS is about theory and how you model it.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

Back to comp.compilers | Previous | Next — Next in thread | Find similar

Thread

Integer sizes and DFAs Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-26 17:16 +0200
  Re: Integer sizes and DFAs Kaz Kylheku <480-992-1380@kylheku.com> - 2022-03-26 18:39 +0000

csiph-web