Finally learning C++!

[maddog]

the Event Queue, whether round-robin, preemptive, or EDF or a combination of thereof is a subpart of a kernel, kernel is responsible for process handling, memory management, low-level io operations, process resource allocation, file system, etc, etc. RTOS is still an os, still runs some form of a kernel...

On this I totally agree.

In plainest terms, no matter what the os, as long as there is a shell (in whatever form), there's some form of a kernel (get it, kernel, shell.....)

An OS may or may-not have a shell. An embedded system with no IO interface such as a keyboard/display can still run processes in Real-Time.

OS X is actually not RTOS, though i am not sure if you said that, or if i didn't understand you...

I don't think I did say that, though in the center of Mac OS X is the MachKernel which does schedule things real-time though not as stringent as a True RTOS.

 

However it runs circles around Windows as an OS in keeping deadlines set and scheduled.

OS X actually runs XNU kernel (developed by Steve's buddies at NeXT, its a mach 3 microkernel with BSD process model, network stack and VFS, and I/O Kit (really nice device driver framework)).

That is true only so far as the processes around the Kernel. The project by Carnegie-Mellon called the MachKernel is it's core.

It's not a linux-like layer, its unix subsystem in its purest form with a microkernel at the base and brilliant OO device management, all wrapped in an Apple GUI (sounds like a pie recipe or something)) :)

On this I totally agree.

 

:hihi:

 

maddog

 

ps: The RTOS examples I was using were only GHS Integrity / Wind River VxWorks. :)

[Symbology]

When I was in console operations 15 years ago on the IBM 3990 mainframe, running the Z90 operating system, the kernel fit on a floppy. When the hardware was changed out, a new floppy had to be inserted and system booted off of floppy prior to loading the Operating System - which did not have to change. In addition there were times that the Kernel itself got patched and we had to reboot with a new floppy. Again the Operating System did not change. It had it's own load process off the the large tape drives.

 

In addition I had a friend that worked on AMD systems. It also ran the Z90 operating system. And it had a different Kernel that mapped to the AMD hardware.

 

I expect that the new ZOS loads off of a memory stick or similar these days, I don't know. But I would bet an ample amount of money that the Kernel and the Operating System still load separately.

 

Other various sources on the web will point out that Kernel is always in memory and is never swapped out, whereas under heavy loads, portions of the Operating System will get paged out.

 

A Kernel and an OS have a clear division line. That is the whole point of having a kernel. Otherwise it would just be some set of IO modules in the total OS.

 

I realize that small OS systems like Windows have it all loaded on one install disk. That is because the OS is designed to only work on Intel based hardware. That does not mean that the Kernel and the OS are one in the same.

[alexander]

no, kernel is the OS, the interface, is just that, an interface... Linux is a kernel, it is just that, like the first floppy, the rest is software... you can keep the software the same as you update and change the kernel, granted that ofcourse no changes to api calls were made, but those are fairly standardized, the software is not the OS, the Kernel (at least monolithic, well in microkernels like os x, XNU is considered to be the kernel, even though it consistent of a microkernel and add-on modules...) IS the OS...

 

Windows has a kernel, it is loaded by the boot loader, you can have an OS without a kernel, it's the MOST defining structure of an OS, what makes an os an os; some updates patch and update the windows kernel that is loaded by the microsoft boot loader, you dont see it being done with shiny graphics on top and microsoft's everything built-in approach, but the kernel is a separate and integrated part of Windows, it is the core of the OS, any OS, the rest is the interface and the rest of the software that might be distributed with the os... gaaaah why are we caught on this?

[alexander]

Think of it this way, i mean i have no other way i can cmmunicate this i guess

 

expressing OS and its components mathematically:

 

[math]O_s=\sqrt{K_e} + S_h + A_p[/math]

 

Ke = kenrel

Sh = shell (command line or graphical)

Ap = Applications

 

for any variable that exists, value is positive, for any variable that does not exist, value is negative...

[maddog]

When I was in console operations 15 years ago on the IBM 3990 mainframe, running the Z90 operating system, the kernel fit on a floppy. When the hardware was changed out, a new floppy had to be inserted and system booted off of floppy prior to loading the Operating System - which did not have to change. In addition there were times that the Kernel itself got patched and we had to reboot with a new floppy. Again the Operating System did not change. It had it's own load process off the the large tape drives.

 

In addition I had a friend that worked on AMD systems. It also ran the Z90 operating system. And it had a different Kernel that mapped to the AMD hardware.

:naughty:

 

I believe what you are referring to is a "boot loader". Older OS's had (due to Lack of Device Drivers) partitioned the Operating System to bring a system up (as it was Very Complicated). I remember when I was waaaay younger. I worked in manufacturing at Atari (yeah I did work there) where they had PDP 8 for running the Automated Insertion Machines and Automated Sequencers. To bring that machine up was a reel hassle. This was back in the days when "PowerOn" did not just mean "flipping a switch". I would suspect with a mainframe it was even worse. In my PDP8 example, the was a front panel, where I would input a command sequence on flipswitches. This was enough to run a PaperTape BootLoader. From there (bootloader) code on the tape was enough to access the rest of the OS on the Hard Drive (yeah we had one -- a whole 10 MB). So your BootLoader is/was more Advanced, it was run on a Floppy. Still the same principle.

 

You cannot compare the methods of how mainframe (and older mini's for that matter) do exactly the same thing as micros (same in principle maybe slightly different in execution).

 

That is why Alexander's example of the BIOS on a PC is just like the BootLoad; the PowerSupply gives current to the motherboard with an AutoVector to start the BIOS which loads the Windows Kernel (better partitioned in NT). The older MS versions with DOS was just like your floppy version. Windows 3.11 was Really a fancy app that allowed a full environment for a user to do work. This Solaris and Linux also have layers. You can think of this a two step process. Yet to distinguish the Kernel as separate from the rest of the OS is mostly fallacious for Micros.

 

I expect that the new ZOS loads off of a memory stick or similar these days, I don't know. But I would bet an ample amount of money that the Kernel and the Operating System still load separately.

I doubt that IBM has updated their IBM 3990 mainframe much beyond what you use and has long since got minimal support. IBM is pushing Blade Servers running some variant of Linux. It just runs you never notice, just login.

 

Other various sources on the web will point out that Kernel is always in memory and is never swapped out, whereas under heavy loads, portions of the Operating System will get paged out.

There I agree with you the Paging process is prevented from swapping out the Kernel.

For both Green Hills Integrity and Wind River VxWorks for example when I make a monolithic image (I am building the whole enchilada). This is an Embedded example like say a Microwave, TV set or a missle. Take your pick when something is set to go and there are no drives to load, it's all-in-one. Still you do treat the kernel separate even though it is together.

 

maddog

[maddog]

microkernels like os x, XNU is considered to be the kernel, even though it consistent of a microkernel and add-on modules...) IS the OS...

I forgot all about the terminology of a "microkernel". Yes, you were right that is what is embedded in Mac OS X. I think I was talking a little history about the initial R&D Project at Carnegie-Mellon called the MachKernel -- that Steve Jobs when at NeXT put in Their OS.

 

Funny how are brain forgets those things. :naughty:

 

maddog

[alexander]

lol yeah maddog, it gets uber confusing when they take a kernel, add some extensions to it and rename it to something different, and we (the end users) somehow have to keep track of all of that :)

 

anyways, anyone following the Haiku project? They announced last year (april-ish) that the OS was finally self-hosting and you can now download development images, it seems like a very cool idea (meh loves BeOS) :) btw haiku is a BeOS-inspired project released under the MIT license...

 

btw, operating systems are all loaded via a boot loader, unless they are built as firmware on a micro-controller, in which case its fired off like bios, it's loaded with a boot loader, in linux you have a choice of boot loaders to use (e.g. GRUB, Lilo, Syslinux, LoadLin or even kernel's own LBS), in windows its somewhat internally built in, but even though you don't see it as a separate part it still does what a boot loader does, infact you know boot.ini on the root of C? yeah, its a boot loader configuration file... (and yes mac os also has a boot loader, what a surprise, i know ;) - System Startup Programming Topics: The Boot Process )

 

enjoy :)

[IDMclean]

Hi people,

I'm taking Programming and Algorithms II at school, and we're using c++. I've gotten obsessed over this prime number hunting program, and I thought I would share it here for feedback.

 

#include <string>
#include <sstream>

unsigned long number;
string digits;
sstream converter;
unsigned long table [uSHRT_MAX];

for(int i = 0; i < USHRT_MAX;)
If ( number & 1 ) {
  converter << number;
  digits = converter.str();
  
  if ( digits[digits.length-1] != 5 ){
     table[i] = number;
     i++;
  }
}
//My apologies ahead of time, but my coding environment at home is broken, so I am unable to test anything. I'll make corrections to the above code as I make them and test them, or as I get submissions.
//Finally, the above code is what is sufficient to get this part to work, but the algorithm itself will need to be dropped into a function, and it will fail to produce visible output, so you may want to put some output code.

 

This is the first part. It generates a list of numbers which end in 1, 3, 7, or 9. This list is then supposed to be put through a primality test. For now, I am going to implement a modified Sieve of Eratosthenes to check my list for primes.

 

So far, in looking around the web, I like the implementation done by Mariano Abdala at CodeProject, but for my purposes, it needs to be modified to work with my Odd-5 set. I love the idea of using an array of bits or of booleans and then flagging them as multiples for batch elimination later.

 

My greatest challenge is how to structure the data so I will use what I need and no more than that. I've been dreaming up a combination Vector & Singlely Linked List to build my number & boolean set, but it's conceptual at this point. I would appreciate any coded concepts towards structuring this to deal with arbitrarily large prime numbers and number sets (sequences?).

 

Alex and Buffy, I expect that the both of you will have much to contribute. :naughty:

Thanks everyone,

-The Clown

[alexander]

here is a simplistic way of testing for primity:

bool is_prime(int num)
{
   //lets see we need to check for a couple of things first
   if ( num==2 || num==3 || num==5 || num==7 )
   {
        return true;
   }
   if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7=0)
   {
       return false;
   }

   int i=0;
   //leaves us with only needing to check the odds odds

   for ( i = 11; j<=(num+1)/2; i=i+2 )
   {
       if( i%3==0 || i%5==0 || i%7==0)
       {
            continue;
       }
       if ( ! ( num % i ) )
       {
            return false;
       }
   }
   return true;
}

 

this is probably the faster way to check for primity with the fewest iterations

 

actually really thinking about this, didn't all primes above 3 fall into the category of 6*n+1 or 6*n-1.... if so why don't we just check for that? sems like that would weild a hell of a lot faster whether or not a number is prime, no?

 

//This code is highly experimental!!! do not try at home

bool is_prime(int num)
{
   //lets see we need to check for a couple of things first
   if ( num==2 || num==3 || num==5 || num==7 )
   {
        return true;
   }
   if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7=0)
   {
       return false;
   }

   if((num+1)%6==0 || (num-1)%6==0)
   {
       return true;
   }
   return false
}

[alexander]

experimental working C++ code for testing for primity, speed is the same for any number under 10 digits... tested with a random assortment of 50 of prime numbers from 1 = 999999999

 

#include <iostream>

using std::cin;
using std::cout;

//This code is highly experimental!!! do not try at home

bool is_prime(int num)
{
   //lets see we need to check for a couple of things first
   if ( num==2 || num==3 || num==5 || num==7 )
   {
        return true;
   }
   if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7==0)
   {
       return false;
   }

   if((num+1)%6==0 || (num-1)%6==0)
   {
       return true;
   }
   return false;
}

int main()
{
int num;

while(1)
{
	cout << "Gimme a prime or type in 0 to exit: ";
	cin >> num;

	if (num==0)
	{
		return 0;
	}

	if (is_prime(num)==true)
	{
		cout <<"n It's Primen";
	}
	else
	{
		cout << "n It's not-so-primen";
	}
}
}

 

how much you wanna bet nobody in your class would have though of that?

[alexander]

even more optimized

bool is_prime(unsigned int num)
{
   static bool firstPrimes[] = {false, false, true, true, false, true, false, true};
   
   if (num < 8)
       return firstPrimes[num];

   if (num%2==0 || num%3==0 || num%5==0 || num%7==0)
       return false;

   if ((num + 1)%6 == 0 || (num - 1)%6 == 0)
       return true;
   
   return false;
}

[alexander]

ok, found a problem with the algorithm... need to figure out how to fix it efficiently

 

gotta run home.. i already have ideas

[alexander]

bool is_prime(int num)
{
 //lets see we need to check for a couple of things first
 static bool firstPrimes[] = {false, false, true, true, false, true, false, true};
 if (num < 8)
   {
     return firstPrimes[num];
   }

 if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7==0 || int(sqrt(num))==sqrt(num))
   {
     return false;
   }
 
 if((num+1)%6==0 || (num-1)%6==0)
   {
     return true;
   }
 return false;
}

new code... current problem is, if the number's only factors are primes, it's falsely identified

[alexander]

Ok, not quite there, but this is an improved algorithm, versus traditional techniques, this will significantly reduce the amount of processing needed to generate, or check for a prime...

 

bool is_prime(int num)
{
 //lets see we need to check for a couple of things first
 static bool firstPrimes[] = {false, false, true, true, false, true, false, true};
 if (num < 8)
   {
     return firstPrimes[num];
   }

 if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7==0 || int(sqrt(num))==sqrt(num))
   {
     return false;
   }
 
 if((num+1)%6==0 || (num-1)%6==0)
   {
     int i=0;
     for(i=11; i<sqrt(num+1); i=i+2)
{
  if(num%i==0)
    {
      return false;
    }
}
     return true;
   }
 return false;
}

[alexander]

ok so here are two test programs:

 

traditional prime number finder (from 1 to 100000)

#include <iostream>
#include <math.h>

using std::cout;

//This code is highly experimental!!! do not try at home

bool is_prime(int num)
{
 if(num==0 || num==1)
   {
     return false;
   }
 for(int i=2; i<sqrt(num+1); i++)
   {
     if(num%i==0)
{
  return false;
}
   }
 return true;
}

int main()
{
 int num=0;
 for( num=1; num<=100000; num++)
   {
     if(is_prime(num))
{
  cout << num << "n";
}
   }
 return 0;
}

 

my method:

#include <iostream>
#include <math.h>

using std::cout;

//This code is highly experimental!!! do not try at home

bool is_prime(int num)
{
 //lets see we need to check for a couple of things first
 
 //compare to single digit primes, why? they are the only ones with irreglarities
 if (num < 8)
   {
     static bool firstPrimes[] = {false, false, true, true, false, true, false, true};
     return firstPrimes[num];
   }
   
 //now lett's check for simple division, this weeds out a LOT of numbers
 if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7==0)
   {
     return false;
   }
 
 //exploiting what we know about the prime set, weed out even MORE numbers
 if((num+1)%6==0 || (num-1)%6==0)
   {
     //unfortunately we still need to do this, this is the only way to check if the number has prime factors...
     for(int i=11; i<sqrt(num+1); i=i+2)
  {
    if(num%i==0)
      {
        return false;
      }
  }
     return true;
   }
 return false;
}
 
int main()
{
 int num;

  for( num=0; num<=100000; num++)
    {
      if(is_prime(num))
	{
	  cout << num << "n";
	}
    }
  return 0;
}

 

give them a spin, i think you will find my code be about .1 to .15ms faster (on a run that takes about .2-.25 ms for my version and .35-.4ms for standard code

[alexander]

ok modified the scripts to run to a mill, run them 5 times and do an average time value that way:

 

traditional

runtime - 0m22.853s

average run time 4.5706s

 

my method

runtime - 0m14.981s

average run time 2.9962s

[IDMclean]

Hi et all,

I apologize for the tardiness of my reply. I'll take a look at your implementation of a primality test today.

 

I've been working on my own implementation diligently. Here's my code:

 

#include <iostream>
#include <climits>
#include <math.h>

int main(){
   int alength = USHRT_MAX;
   unsigned long e[alength];
   unsigned long xchange[alength];


//This is my odd-5 set generator. It works really quickly, right now it uses a static array.
for(unsigned long i = 0, number = 3; i < alength; number+=2) {
	if(number%5) {
	    e[i]=number;
	    i++;
	    }
}

//Sets bounds for the Sieve of Eratosthenes
   unsigned long ibounds = sqrtl(e[alength-1]);
//Begins sieving by a modified Eratosthenes algorithm, skips powers of primes at this stage. It marks non-primes as false.
for(unsigned long i = 0; e[i] < ibounds;i++){
       if(e[i] != 0) for(unsigned long j = i+1, m=(i*j)+1, r = 0;r < e[alength-1] && j < alength;){
           if(e[j] != 0){
               r = e[i]*e[j];
               bool flagged = true;
               while(flagged && m < alength && e[m] <= r && r < e[alength-1]){
                   if(e[m] == r){
                       e[m] = 0;
                       flagged = false;
                       j++;
                   }else m++;
               }
           }else j++;

       }
   }

//This sieves through the powers of primes and marks them false.
   for(unsigned long i = 0; e[i] < ibounds;i++){
       if(e[i] != 0) for(unsigned long j = 2, m = 0, r = 0;e[alength-1] && r < e[alength-1]; j++){
           r = powl(e[i], j);
           bool flagged = true;
           while(flagged && m < alength && e[m] <= r && r <= e[alength-1]){
               if(e[m] == r){
                   e[m] = 0;
                   flagged = false;
                   m++;
               }else m++;
           }
       }
   }

//Compacts the set by eliminating the false elements. By current setup, it will produce just under 15000 primes in about .2 seconds. The data structure limits the number of primes that can be searched for and found at current.
   for (unsigned long i = 0, j=0; i < alength; i++) {
       if(e[i]){
       xchange[j] = e[i];
       j++;
       }
}

//This prints the primes in the compacted array. It takes about 5 seconds on my machine.
for (unsigned long i = 0;xchange[i] && i < alength; i++) {
       std::cout << "Prime number: " << i << " is " << xchange[i] << std::endl;
}
}

 

I know it could be a lot more concise; I'm working on refactoring the program and altering my data structure for scalability. I'm going to use a bit-array/vector. I'd like to work on the elimination algorithm. If the m index starts somewhere below or at the index of the element I am searching for, the program will mark off non-primes faster.

 

Sadly, My algebra teacher skipped over matrix mathematics because quote: "You will never use this stuff."

 

Cheers,

-The Clown