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

Groups > comp.lang.c > #59944 > unrolled thread

primitive instruction for programming

Back to article view | Back to comp.lang.c

Contents

  primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 00:56 -0700
    Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-13 09:24 +0100
      Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 01:59 -0700
        Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-13 10:32 +0100
          Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 02:53 -0700
            Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 11:04 +0100
            Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-13 14:10 +0200
              Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-20 14:27 -0700
                Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-20 15:12 -0700
                  Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-21 00:17 +0100
                    Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-22 11:07 -0700
                Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 09:04 +0200
                  Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-21 03:02 -0500
                  Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-21 01:34 -0700
                    Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 11:34 +0200
                      Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-21 11:48 +0100
                        Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 13:10 +0200
                    Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-21 10:53 +0100
      Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 20:09 +0100
        Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 12:48 -0700
        Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 09:40 +0200
          Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-14 11:24 +0100
            Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-14 05:39 -0500
            Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 13:29 +0200
    Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 10:59 +0100
      Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 03:28 -0700
        Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 03:33 -0700
          Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 03:59 -0700
            Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 04:23 -0700
        Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 11:36 +0100
          Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 04:26 -0700
            Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 12:41 +0100
              Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 06:26 -0700
                Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-13 15:33 +0200
                  Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 06:44 -0700
                    Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-13 16:30 +0200
                      Re: primitive instruction for programming Ian Collins <ian-news@hotmail.com> - 2015-04-14 07:52 +1200
                        Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 09:47 +0200
                          Re: primitive instruction for programming raltbos@xs4all.nl (Richard Bos) - 2015-04-14 08:10 +0000
                            Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 10:40 +0200
          Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-13 17:52 +0000
            Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-13 18:20 -0500
              Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-13 18:33 -0500
                Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-14 19:51 +0000
            Re: primitive instruction for programming Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-16 09:04 -0700
              Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-17 02:25 +0000
                Re: primitive instruction for programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-17 08:34 -0700
                  Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-17 17:49 +0100
                  Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-17 19:06 +0000
                    Re: primitive instruction for programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-17 20:45 -0700
                      Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-18 16:43 +0000
                        Re: primitive instruction for programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-18 09:56 -0700
                  Re: primitive instruction for programming Stephen Sprunk <stephen@sprunk.org> - 2015-04-17 17:52 -0500
                    Re: primitive instruction for programming Morris Dovey <mrdovey@iedu.com> - 2015-04-17 18:02 -0500
                      Re: primitive instruction for programming Stephen Sprunk <stephen@sprunk.org> - 2015-04-17 19:26 -0500
                        Re: primitive instruction for programming Morris Dovey <mrdovey@iedu.com> - 2015-04-17 20:04 -0500
                    Re: primitive instruction for programming Michael Angelo Ravera <maravera@prodigy.net> - 2015-04-19 14:59 -0700
                      Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-20 00:19 +0100
                        Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-20 02:06 +0100
                          Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-20 02:26 +0100
                          Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-20 02:18 +0100
                Re: primitive instruction for programming Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-18 18:59 -0700
                  Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-19 16:28 +0000
                    Re: primitive instruction for programming Richard Damon <Richard@Damon-Family.org> - 2015-04-19 17:16 -0400
                    Re: primitive instruction for programming Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-22 15:28 -0700
            Re: primitive instruction for programming John Bode <jfbode1029@gmail.com> - 2015-04-23 07:20 -0700
    Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 03:07 -0700
      Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 09:47 -0700
        Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 11:09 -0700
          Re: primitive instruction for programming Noob <root@127.0.0.1> - 2015-04-13 20:43 +0200
            Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 12:09 -0700
              Re: primitive instruction for programming Xcott Craver <xcottcraver@gmail.com> - 2015-04-14 07:11 -0700
                Re: primitive instruction for programming fmassei@gmail.com - 2015-04-14 07:28 -0700
                  Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-14 15:57 +0100
                    Re: primitive instruction for programming fmassei@gmail.com - 2015-04-14 08:13 -0700
        Re: primitive instruction for programming fir <profesor.fir@gmail.com> - 2015-04-13 14:02 -0700
          Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 14:28 -0700
            Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 22:51 +0100
              Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 14:58 -0700
                Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 23:25 +0100
                  Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 15:37 -0700
                    Re: primitive instruction for programming James Kuyper <jameskuyper@verizon.net> - 2015-04-13 19:09 -0400
                      Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 16:20 -0700
                  Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-13 18:03 -0500
              Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 20:58 -0700
            Re: primitive instruction for programming fir <profesor.fir@gmail.com> - 2015-04-13 15:02 -0700

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

#59973

On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote:
> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote:
> >Bartc wrote:
> >"
> >count=0;
> >n=500;
> >for (a=1; a<=n; ++a)
> >     for (b=a; b<=n; ++b)
> >        for (c=b; c<=n*2; ++c)
> >           if (a*a+b*b==c*c)
> >              ++count;
> >
> >
> >printf("Count = %d\n",count);
> >"
> >Easy would be something as:
> >count=0; n=500;
> >     a=1; G(1,l0);
> >a0:   b=0; G(1,l1);
> >a1:     c=b; G(1,l3);
> >a3:       G(!(a*a+b*b==c*c),l4); ++count;
> >l4:     ++c;
> >l3:     G(c<=n*2, a3);
> >       ++b;
> >l2:   G(b<=n, a1);
> >     ++a;
> >l0: G(a<=n, a0);
> >printf("Count = %d\n",count);
> >
> 
> "label l1 not defined".
> 
> This style of code is more error-prone. It's not even obvious where l1 
> needs to go; I can put it in several places and it would still compile, 
> but the program won't work.
> 
> This is something that just isn't a problem when using conventional 
> control structures; why do you want to introduce a new source of bugs?

One of the things I've been trying to do is an inorder traversal of a
binary tree without using recursion.  With normal control structures
it doesn't seem possible without using goto.



Regards,

Steve Thompson

-- 
"If I had a nickel for every time some idiot called me about a
computer problem that turned out to be user error, I would be able to
retire and spend the rest of my days cultivating clues in my backyard
hillside garden."  -- MysteryDog in 24hoursupport.helpdesk.

[toc] | [prev] | [next] | [standalone]

#59995

On Mon, 13 Apr 2015 17:52:40 +0000, Steve Thompson
<stevet810@gmail.com> wrote:

>On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote:
>> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote:
>> >Bartc wrote:
>> >"
>> >count=0;
>> >n=500;
>> >for (a=1; a<=n; ++a)
>> >     for (b=a; b<=n; ++b)
>> >        for (c=b; c<=n*2; ++c)
>> >           if (a*a+b*b==c*c)
>> >              ++count;
>> >
>> >
>> >printf("Count = %d\n",count);
>> >"
>> >Easy would be something as:
>> >count=0; n=500;
>> >     a=1; G(1,l0);
>> >a0:   b=0; G(1,l1);
>> >a1:     c=b; G(1,l3);
>> >a3:       G(!(a*a+b*b==c*c),l4); ++count;
>> >l4:     ++c;
>> >l3:     G(c<=n*2, a3);
>> >       ++b;
>> >l2:   G(b<=n, a1);
>> >     ++a;
>> >l0: G(a<=n, a0);
>> >printf("Count = %d\n",count);
>> >
>> 
>> "label l1 not defined".
>> 
>> This style of code is more error-prone. It's not even obvious where l1 
>> needs to go; I can put it in several places and it would still compile, 
>> but the program won't work.
>> 
>> This is something that just isn't a problem when using conventional 
>> control structures; why do you want to introduce a new source of bugs?
>
>One of the things I've been trying to do is an inorder traversal of a
>binary tree without using recursion.  With normal control structures
>it doesn't seem possible without using goto.


Depending on how you want to parse "without gotos", you can do that by
faking gotos with an infinite loop around a case statement.

In any event, it's not hard to do with an explicitly managed stack.
Consider a stack that has pairs of items, a work type and a node
pointer.  Do something like:


node = rootnode;
push (end, NULL);

for(;;)
{
  pop item
  if (item.type == end) break;
  if (item.type == traverse)
    {
    if (item.node != NULL)
      {
      push (traverse, item.node->right);
      push (output, item.node);
      push (traverse, item.node->left);
      }
    }
  if (item.type == output)
    output item.node;
}

[toc] | [prev] | [next] | [standalone]

#59996

On Mon, 13 Apr 2015 18:20:38 -0500, Robert Wessel
<robertwessel2@yahoo.com> wrote:

>On Mon, 13 Apr 2015 17:52:40 +0000, Steve Thompson
><stevet810@gmail.com> wrote:
>
>>On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote:
>>> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote:
>>> >Bartc wrote:
>>> >"
>>> >count=0;
>>> >n=500;
>>> >for (a=1; a<=n; ++a)
>>> >     for (b=a; b<=n; ++b)
>>> >        for (c=b; c<=n*2; ++c)
>>> >           if (a*a+b*b==c*c)
>>> >              ++count;
>>> >
>>> >
>>> >printf("Count = %d\n",count);
>>> >"
>>> >Easy would be something as:
>>> >count=0; n=500;
>>> >     a=1; G(1,l0);
>>> >a0:   b=0; G(1,l1);
>>> >a1:     c=b; G(1,l3);
>>> >a3:       G(!(a*a+b*b==c*c),l4); ++count;
>>> >l4:     ++c;
>>> >l3:     G(c<=n*2, a3);
>>> >       ++b;
>>> >l2:   G(b<=n, a1);
>>> >     ++a;
>>> >l0: G(a<=n, a0);
>>> >printf("Count = %d\n",count);
>>> >
>>> 
>>> "label l1 not defined".
>>> 
>>> This style of code is more error-prone. It's not even obvious where l1 
>>> needs to go; I can put it in several places and it would still compile, 
>>> but the program won't work.
>>> 
>>> This is something that just isn't a problem when using conventional 
>>> control structures; why do you want to introduce a new source of bugs?
>>
>>One of the things I've been trying to do is an inorder traversal of a
>>binary tree without using recursion.  With normal control structures
>>it doesn't seem possible without using goto.
>
>
>Depending on how you want to parse "without gotos", you can do that by
>faking gotos with an infinite loop around a case statement.
>
>In any event, it's not hard to do with an explicitly managed stack.
>Consider a stack that has pairs of items, a work type and a node
>pointer.  Do something like:
>
>
>node = rootnode;
>push (end, NULL);
>
>for(;;)
>{
>  pop item
>  if (item.type == end) break;
>  if (item.type == traverse)
>    {
>    if (item.node != NULL)
>      {
>      push (traverse, item.node->right);
>      push (output, item.node);
>      push (traverse, item.node->left);
>      }
>    }
>  if (item.type == output)
>    output item.node;
>}


Code in haste, repent in leisure....

You have to actually put the root node on the stack in there
somewhere, with something like a:

  push (traverse, rootnode);

before the loop.

[toc] | [prev] | [next] | [standalone]

#60053

On Mon, Apr 13, 2015 at 06:33:38PM -0500, Robert Wessel wrote:
> On Mon, 13 Apr 2015 18:20:38 -0500, Robert Wessel
> <robertwessel2@yahoo.com> wrote:
> 
> Code in haste, repent in leisure....
> 
> You have to actually put the root node on the stack in there
> somewhere, with something like a:
> 
>   push (traverse, rootnode);
> 
> before the loop.

So, your code should then look like:

>  node = rootnode;
>  push (end, NULL);
>  push (traverse, rootnode);
>  
>  for(;;)
>  {
>    pop item
>    if (item.type == end) break;
>    if (item.type == traverse)
>      {
>      if (item.node != NULL)
>        {
>        push (traverse, item.node->right);
>        push (output, item.node);
>        push (traverse, item.node->left);
>        }
>      }
>    if (item.type == output)
>      output item.node;
>  }

I can sort of see how that works, although your push and pop macro/
functions are not so clear but that is only a detail. I ought to have
implied that I merely had difficulty generating the algorithm without
gotos, as I have succeeded with (simplified):


    p = tree->root;

l1:
    if(p->left) {
        push(p, LEFT);
        p = p->left;
        goto l1;
    }

l2:
    do_something_to(p);

    if(p->right) {
        push(p, RIGHT);
        p = p->right;
        goto l1;
    }

l3:
    if(p == tree->root)
        goto next:

    pop(p, dir);

    if(dir == LEFT)
        goto l2;
    else
        goto l3;

next:


... which is reasonably straightforward but is bound to provoke people
who unconditionally dislike goto.  GCC allows one to take the address
of a label and so one can do something like the following:

   void *addr;

   p = tree->root;

l1:
    if(p->left) {
        push(p, &l2);
        p = p->left;
        goto l1;
    }

l2:
    do_something_to(p);

    if(p->right) {
        push(p, &l3);
        p = p->right;
        goto l1;
    }

l3:
    if(p == tree->root)
        goto next:

    pop(p, addr);

    goto *addr;


But the above reduces portability so I just use an int and the
comparison as in the first example.  The hard pard was finessing GCC
to allow using the processor stack as opposed to a stack-like
structure.



Regards,

Steve Thompson

-- 
"If I had a nickel for every time some idiot called me about a
computer problem that turned out to be user error, I would be able to
retire and spend the rest of my days cultivating clues in my backyard
hillside garden."  -- MysteryDog in 24hoursupport.helpdesk.

[toc] | [prev] | [next] | [standalone]

#60148

Steve Thompson <stevet810@gmail.com> writes:

> On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote:
>> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote:
>>> Bartc wrote:
>>> [code example that uses labels and goto's]
>>
>> This style of code is more error-prone.  It's not even obvious
>> where l1 needs to go;  I can put it in several places and it would
>> still compile, but the program won't work.
>>
>> This is something that just isn't a problem when using conventional
>> control structures;  why do you want to introduce a new source of
>> bugs?
>
> One of the things I've been trying to do is an inorder traversal
> of a binary tree without using recursion.  With normal control
> structures it doesn't seem possible without using goto.

This is an interesting problem.  It has a solution that is
fairly simple but not immediately obvious.  The key idea is
to keep track of two different kinds of state - a (pointer to
a) tree which represents a completely unprocessed subtree,
and a stack of (pointers to) trees which represent subtrees
that have had their left sides taken care of but still need
their value processed and their right side done;  loop over
processing those as long as the unprocessed subtree is
non-empty or the stack is non-empty, always processing an
unprocessed subtree first.  Here is a function to illustrate
that does inorder printing (the Index type is just an
ordinary integer type;  note that the type Tree is a pointer
type, so the 'stack' variable is a pointer to an array of
pointers):

    void
    inorder_print( Tree root ){
        Tree *stack = malloc( 100 * sizeof *stack );
        Index next = 0;
        Tree tree = root;

        while(  tree  ||  next > 0  ){
            if(  tree  ){
                stack[ next++ ] = tree;
                tree = tree->left;
            } else {
                tree = stack[ --next ];
                printf( " %d", tree->value );
                tree = tree->right;
            }
        } 
        printf( "\n" );

        free( stack );
    }

[toc] | [prev] | [next] | [standalone]

#60232

On Thu, Apr 16, 2015 at 09:04:34AM -0700, Tim Rentsch wrote:
> Steve Thompson <stevet810@gmail.com> writes:
> 
> > On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote:
> >> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote:
> >>> Bartc wrote:
> >>> [code example that uses labels and goto's]
> >>
> >> This style of code is more error-prone.  It's not even obvious
> >> where l1 needs to go;  I can put it in several places and it would
> >> still compile, but the program won't work.
> >>
> >> This is something that just isn't a problem when using conventional
> >> control structures;  why do you want to introduce a new source of
> >> bugs?
> >
> > One of the things I've been trying to do is an inorder traversal
> > of a binary tree without using recursion.  With normal control
> > structures it doesn't seem possible without using goto.
> 
> This is an interesting problem.  It has a solution that is
> fairly simple but not immediately obvious.  The key idea is
> to keep track of two different kinds of state - a (pointer to
> a) tree which represents a completely unprocessed subtree,
> and a stack of (pointers to) trees which represent subtrees
> that have had their left sides taken care of but still need
> their value processed and their right side done;  loop over
> processing those as long as the unprocessed subtree is
> non-empty or the stack is non-empty, always processing an
> unprocessed subtree first.  Here is a function to illustrate
> that does inorder printing (the Index type is just an
> ordinary integer type;  note that the type Tree is a pointer
> type, so the 'stack' variable is a pointer to an array of
> pointers):

That is a succint description.  As I wrote in a followup I should have
clarified that I found an algorithm, but it is rather goto oriented.

>     void
>     inorder_print( Tree root ){
>         Tree *stack = malloc( 100 * sizeof *stack );

A balanced binary tree with a depth of 90 will easily exceed the
number of nodes one might hope to address with a 64-bit address space.
If the tree is unbalanced you should guard against stack overflow or
make sure that your insert/delete functions catch this.

>         Index next = 0;
>         Tree tree = root;
> 
>         while(  tree  ||  next > 0  ){
>             if(  tree  ){
>                 stack[ next++ ] = tree;
>                 tree = tree->left;
>             } else {
>                 tree = stack[ --next ];
>                 printf( " %d", tree->value );
>                 tree = tree->right;
>             }
>         } 
>         printf( "\n" );
> 
>         free( stack );
>     }

I think one of the lessons here is that parent pointers are pretty
much superfluous to binary tree algorithms, and that recursion is
mostly avoidable.




Regards,

Steve Thompson

-- 
"If I had a nickel for every time some idiot called me about a
computer problem that turned out to be user error, I would be able to
retire and spend the rest of my days cultivating clues in my backyard
hillside garden."  -- MysteryDog in 24hoursupport.helpdesk.

[toc] | [prev] | [next] | [standalone]

#60241

On Friday, April 17, 2015 at 3:35:46 PM UTC+1, Steve Thompson wrote:
> On Thu, Apr 16, 2015 at 09:04:34AM -0700, Tim Rentsch wrote:
> 
> >     void
> >     inorder_print( Tree root ){
> >         Tree *stack = malloc( 100 * sizeof *stack );
> 
> A balanced binary tree with a depth of 90 will easily exceed the
> number of nodes one might hope to address with a 64-bit address space.
> If the tree is unbalanced you should guard against stack overflow or
> make sure that your insert/delete functions catch this.
> 
The human/chimp split was about 5 million years ago.
A generation is about 20 years, and the population was low by modern standards 
until the development of agriculture, maybe 10,000 year ago.
So let's say 250,000 generations with a population of 100,000, and
200 generations with a population of 1 billion, plus 10 billion for the 20th
century. 
250,000 * 100,000 + 200 * 1,000,000,000 + 10,000,000,000

25 billion + 200 billion + 10 billion = 235 billion, so we need about a
terabyte of memory to store a tree consisting of every human who ever lived.
That's a bit expensive, but not unfeasible, we could build such a computer
for low millions of dollars.

Now my parents and grandparents are a perfectly balanced binary tree with one
female and one male entry at each node, and we can hold it in memory.
But the depth is 250,000 until you come to chimpanzees.

[toc] | [prev] | [next] | [standalone]

#60246

On 17/04/2015 16:34, Malcolm McLean wrote:
> On Friday, April 17, 2015 at 3:35:46 PM UTC+1, Steve Thompson wrote:

>> A balanced binary tree with a depth of 90 will easily exceed the
>> number of nodes one might hope to address with a 64-bit address space.
>> If the tree is unbalanced you should guard against stack overflow or
>> make sure that your insert/delete functions catch this.
>>
> The human/chimp split was about 5 million years ago.
> A generation is about 20 years, and the population was low by modern standards
> until the development of agriculture, maybe 10,000 year ago.
> So let's say 250,000 generations with a population of 100,000, and
> 200 generations with a population of 1 billion, plus 10 billion for the 20th
> century.
> 250,000 * 100,000 + 200 * 1,000,000,000 + 10,000,000,000
>
> 25 billion + 200 billion + 10 billion = 235 billion, so we need about a
> terabyte of memory to store a tree consisting of every human who ever lived.
> That's a bit expensive, but not unfeasible, we could build such a computer
> for low millions of dollars.

Does it need to be all in RAM at the same time? 1TB is easily available 
otherwise. A 1TB drive is inexpensive. 1TB RAM wouldn't be that much 
either, unless people are paying over $1000 per GB these days.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#60257

On Fri, Apr 17, 2015 at 08:34:07AM -0700, Malcolm McLean wrote:
> On Friday, April 17, 2015 at 3:35:46 PM UTC+1, Steve Thompson wrote:
> > On Thu, Apr 16, 2015 at 09:04:34AM -0700, Tim Rentsch wrote:
> > 
> > >     void
> > >     inorder_print( Tree root ){
> > >         Tree *stack = malloc( 100 * sizeof *stack );
> > 
> > A balanced binary tree with a depth of 90 will easily exceed the
> > number of nodes one might hope to address with a 64-bit address space.
> > If the tree is unbalanced you should guard against stack overflow or
> > make sure that your insert/delete functions catch this.
> > 
> The human/chimp split was about 5 million years ago.
> A generation is about 20 years, and the population was low by modern standards 
> until the development of agriculture, maybe 10,000 year ago.
> So let's say 250,000 generations with a population of 100,000, and
> 200 generations with a population of 1 billion, plus 10 billion for the 20th
> century. 
> 250,000 * 100,000 + 200 * 1,000,000,000 + 10,000,000,000
> 
> 25 billion + 200 billion + 10 billion = 235 billion, so we need about a
> terabyte of memory to store a tree consisting of every human who ever lived.
> That's a bit expensive, but not unfeasible, we could build such a computer
> for low millions of dollars.
> 
> Now my parents and grandparents are a perfectly balanced binary tree with one
> female and one male entry at each node, and we can hold it in memory.
> But the depth is 250,000 until you come to chimpanzees.

I am failing to grasp your point, although I confess that I have not
tried very hard.

2^90 is 1 237 940 039 285 380 274 899 124 224, a quantity that is
slightly more than 235 billion.

Just to confuse matters: an AVL tree with depth 90 will hold a minimum
of 12 200 160 415 121 876 737 nodes.  Note that is *minimum*.

(2^64 - 1) = 18 446 744 073 709 551 615




Regards,

Steve Thompson

-- 
"If I had a nickel for every time some idiot called me about a
computer problem that turned out to be user error, I would be able to
retire and spend the rest of my days cultivating clues in my backyard
hillside garden."  -- MysteryDog in 24hoursupport.helpdesk.

[toc] | [prev] | [next] | [standalone]

#60291

On Friday, April 17, 2015 at 8:08:46 PM UTC+1, Steve Thompson wrote:
> On Fri, Apr 17, 2015 at 08:34:07AM -0700, Malcolm McLean wrote:
> 
> I am failing to grasp your point, although I confess that I have not
> tried very hard.
> 
> 2^90 is 1 237 940 039 285 380 274 899 124 224, a quantity that is
> slightly more than 235 billion.
> 
You've got two parents, a father and a mother. They also have two parents
each, a father and a mother, giving you four grandparents, eight great-
grandparents, sixteen great great grandparents, and so on.
So we can store a tree with "mummy" and "daddy" pointers. However whilst
incest with close family members is rare, once you get back more than
a few generations you'll start seeing duplicate nodes in the tree.
The same woman might be both your great great great grandmother, and
your great great great great great grandmother via another line.

So whilst we can store the tree, we can't recurse through it all.
We can however find which chimpanzee your Y chromosome was inherited from. 

[toc] | [prev] | [next] | [standalone]

#60326

On Fri, Apr 17, 2015 at 08:45:28PM -0700, Malcolm McLean wrote:
> On Friday, April 17, 2015 at 8:08:46 PM UTC+1, Steve Thompson wrote:
> > On Fri, Apr 17, 2015 at 08:34:07AM -0700, Malcolm McLean wrote:
> > 
> > I am failing to grasp your point, although I confess that I have not
> > tried very hard.
> > 
> > 2^90 is 1 237 940 039 285 380 274 899 124 224, a quantity that is
> > slightly more than 235 billion.
> > 
> You've got two parents, a father and a mother. They also have two parents
> each, a father and a mother, giving you four grandparents, eight great-
> grandparents, sixteen great great grandparents, and so on.
> So we can store a tree with "mummy" and "daddy" pointers. However whilst
> incest with close family members is rare, once you get back more than
> a few generations you'll start seeing duplicate nodes in the tree.
> The same woman might be both your great great great grandmother, and
> your great great great great great grandmother via another line.
> 
> So whilst we can store the tree, we can't recurse through it all.
> We can however find which chimpanzee your Y chromosome was inherited from. 

You can't build the tree.



Regards,

Steve Thompson

-- 
"If I had a nickel for every time some idiot called me about a
computer problem that turned out to be user error, I would be able to
retire and spend the rest of my days cultivating clues in my backyard
hillside garden."  -- MysteryDog in 24hoursupport.helpdesk.

[toc] | [prev] | [next] | [standalone]

#60327

On Saturday, April 18, 2015 at 5:45:44 PM UTC+1, Steve Thompson wrote:
> 
> You can't build the tree.
> 
If you mean, can we genuinely get data on the mother, father and children
of every human who lived from the time of the chimpanzees until now,
then you're right.
But supposing we did have a list, we could easily pass through it setting 
the mummy and daddy pointers from the list of children. It's only
two operations per individual. 

[toc] | [prev] | [next] | [standalone]

#60273

On 17-Apr-15 10:34, Malcolm McLean wrote:
> On Friday, April 17, 2015 at 3:35:46 PM UTC+1, Steve Thompson wrote:
> The human/chimp split was about 5 million years ago.

The most important change was about 1 million years ago, when grasses
appeared--and our ancestors climbed down out of the trees and started
walking upright.  All our other difference vs other primates gradually
developed later as a result of that.

Homo sapiens is only 250,000 - 400,000 years old.  The population was so
tiny back then, though, that varying the start date is probably within
the margin of error anyway.

> A generation is about 20 years, and the population was low by modern
> standards until the development of agriculture, maybe 10,000 year ago.

Right; some religious groups think the world is only 10,000 years old
because that's when agriculture gave our ancestors enough free time to
write history books--and invent religions, rather than spending all
their time just struggling to stay alive long enough to reproduce.

> So let's say 250,000 generations with a population of 100,000, and
> 200 generations with a population of 1 billion, plus 10 billion for
> the 20th century.

World population doubled roughly every 100 years up until 1900, then
started doubling every 25 years, so your math is way off here.

> 25 billion + 200 billion + 10 billion = 235 billion

Most estimates put the number of humans at 100 to 115 billion.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#60274

On 4/17/15 5:52 PM, Stephen Sprunk wrote:
> Most estimates put the number of humans at 100 to 115 billion.

That might be a bit on the high side...

http://www.worldometers.info/world-population/

-- 
Morris Dovey
http://www.iedu.com/Solar/
http://www.facebook.com/MorrisDovey

[toc] | [prev] | [next] | [standalone]

#60283

On 17-Apr-15 18:02, Morris Dovey wrote:
> On 4/17/15 5:52 PM, Stephen Sprunk wrote:
>> Most estimates put the number of humans at 100 to 115 billion.
> 
> That might be a bit on the high side...
> 
> http://www.worldometers.info/world-population/

From that page:

"... it has been estimated that a total of approximately 106 billion
people have been born since the dawn of the human species ..."

That's within the range above.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#60285

On 4/17/15 7:26 PM, Stephen Sprunk wrote:
> On 17-Apr-15 18:02, Morris Dovey wrote:
>> On 4/17/15 5:52 PM, Stephen Sprunk wrote:
>>> Most estimates put the number of humans at 100 to 115 billion.
>>
>> That might be a bit on the high side...
>>
>> http://www.worldometers.info/world-population/
>
>  From that page:
>
> "... it has been estimated that a total of approximately 106 billion
> people have been born since the dawn of the human species ..."
>
> That's within the range above.

My apologies, I misunderstood what you were saying.

-- 
Morris Dovey
http://www.iedu.com/Solar

[toc] | [prev] | [next] | [standalone]

#60470

On Friday, April 17, 2015 at 3:52:50 PM UTC-7, Stephen Sprunk wrote:
> On 17-Apr-15 10:34, Malcolm McLean wrote:
> > On Friday, April 17, 2015 at 3:35:46 PM UTC+1, Steve Thompson wrote:
> > The human/chimp split was about 5 million years ago.
> 
> The most important change was about 1 million years ago, when grasses
> appeared--and our ancestors climbed down out of the trees and started
> walking upright.  All our other difference vs other primates gradually
> developed later as a result of that.
> 
> Homo sapiens is only 250,000 - 400,000 years old.  The population was so
> tiny back then, though, that varying the start date is probably within
> the margin of error anyway.
> 
> > A generation is about 20 years, and the population was low by modern
> > standards until the development of agriculture, maybe 10,000 year ago.
> 
> Right; some religious groups think the world is only 10,000 years old
> because that's when agriculture gave our ancestors enough free time to
> write history books--and invent religions, rather than spending all
> their time just struggling to stay alive long enough to reproduce.
> 
> > So let's say 250,000 generations with a population of 100,000, and
> > 200 generations with a population of 1 billion, plus 10 billion for
> > the 20th century.
> 
> World population doubled roughly every 100 years up until 1900, then
> started doubling every 25 years, so your math is way off here.
> 
> > 25 billion + 200 billion + 10 billion = 235 billion
> 
> Most estimates put the number of humans at 100 to 115 billion.
> 

The 250000 and 400000 year estimates are the limits of our ability to distinguish the DNA lines. Modern humans certainly lived before that, but those of us living today can trace our ancestry to one woman who lived about 250000 years ago and to one man who lived about 400000 years ago (I may have the male and female numbers reversed, but you get the idea). If female generations happened at 20 year intervals, that would give us about 12500 female generations. If male generations happened at 25 year intervals that would give us about 16000 male generations. Our species went through several bottlenecks and nearly vanished about three times (the Biblical account of "The Flood" may be the traditional explanation for one of those bottlenecks. Apparently, the ancients could do the math well enough to figure out that a whole lot of people must once have existed and SOMETHING must have happened)
In the last 10000 or so years (coincident with the warming of the earth) we have been off to the races. Who knows whether our species is responsible for global warming, but global warming is almost certainly responsible for the success of our species! In other words: We didn't make global warming, but global warming made us!
If you skip all of the generations before the warming, we have had time for only 400 or 500 generations.
The best estimates that I have seen put the human population of the earth at approximately 100 million in the first century of the common era, but as far as I know, no one even attempted a full census in China until after Mao (1980). The British may have gotten one done in India just a hundred or so years earlier. The British, Americans, and French (maybe the Swiss) had been doing them for a while before that, but that's three or four countries (at a time where you could probably count at least 2000 independent political entities). My guess is that there are approximately 20 countries in central Africa that have NEVER had a census. So, any estimate of human population before about 1880 should be regarded with quite a bit of skepticism.

[toc] | [prev] | [next] | [standalone]

#60478

On 19/04/15 22:59, Michael Angelo Ravera wrote:
> On Friday, April 17, 2015 at 3:52:50 PM UTC-7, Stephen Sprunk wrote:

<snip>

>> Most estimates put the number of humans at 100 to 115 billion.
<snip>

> [...]  any estimate of human population before about 1880 should
 > be regarded with quite a bit of skepticism.

Fortunately, the situation isn't as bad as all that.

We take the current world population, which is exactly 7238010000.0 at 
the time of writing. We have to multiply this by 1.00000001 every 24 
seconds. So we can find the population at some day in the future (use 
negative arg for the past) with respect to a reference date of today, as 
follows:

#include <math.h>
double population_at(double day)
{
   double curpop = 723801000.0;
   double rateperday = pow(1.00000001, 3600);
   return pow(rateperday, day) * curpop;
}

With a simple main() and binary search, we quickly establish (by 
determining when the population was 2, give or take a rib) that Adam and 
Eve lived about 1500 years ago.

In those days, human pregnancies were considerably longer than nowadays. 
It turns out that Eve was expecting Cain for around 30 years. Abel only 
took about 21 years, and Seth was quicker still (about 22 years).

By Shakespeare's time, the world population was about a quarter of a 
million, and it had reached a million by about 1690.

By the time of the Battle of Waterloo (200 years ago this year), the 
population was 52 million, and by World War I it was almost 200 million.

If we take the average mass of a human being at 50kg (I know, but it 
means I can do at least some of the arithmetic in my head), and the mass 
of the earth at 6E24kg, then the human race will reach one Earth mass at 
a population of 120000000000000000000000, which we'll reach in about the 
year 4531AD. So there's lots of time, and no need to panic.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#60484

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 19/04/15 22:59, Michael Angelo Ravera wrote:
>> On Friday, April 17, 2015 at 3:52:50 PM UTC-7, Stephen Sprunk wrote:
>
> <snip>
>
>>> Most estimates put the number of humans at 100 to 115 billion.
> <snip>
>
>> [...]  any estimate of human population before about 1880 should
>> be regarded with quite a bit of skepticism.
>
> Fortunately, the situation isn't as bad as all that.
>
> We take the current world population, which is exactly 7238010000.0 at
> the time of writing. We have to multiply this by 1.00000001 every 24
> seconds. So we can find the population at some day in the future (use
> negative arg for the past) with respect to a reference date of today,
> as follows:
>
> #include <math.h>
> double population_at(double day)
> {
>   double curpop = 723801000.0;
>   double rateperday = pow(1.00000001, 3600);
>   return pow(rateperday, day) * curpop;
> }
>
> With a simple main() and binary search, we quickly establish (by
> determining when the population was 2, give or take a rib) that Adam
> and Eve lived about 1500 years ago.

I applaud your attempt to shoe-horn some C into this thread, but binary
search?  Seriously?

  log(2 / 723801000.0) / log(pow(1.00000001, 3600))

Replace 2 by the population whose date (in days from today) you want.

<snip>
> If we take the average mass of a human being at 50kg (I know, but it
> means I can do at least some of the arithmetic in my head), and the
> mass of the earth at 6E24kg, then the human race will reach one Earth
> mass at a population of 120000000000000000000000, which we'll reach in
> about the year 4531AD.

I don't get that year.  I get 120000000000000000000000 people in 909493
days from today.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#60485

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 20/04/15 02:06, Ben Bacarisse wrote:
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>
> <snip>
>
>>>
>>> With a simple main() and binary search, we quickly establish (by
>>> determining when the population was 2, give or take a rib) that Adam
>>> and Eve lived about 1500 years ago.
>>
>> I applaud your attempt to shoe-horn some C into this thread, but binary
>> search?  Seriously?
>
> It's been a long day.

Ah, that will explain the discrepancy -- I was assuming all days were
equally long!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web