The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

форумы
правила/FAQ
поиск
регистрация
вход
слежка
RSS


Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

В ядро Linux может быть включен диспетчер реального времени, opennews (??), 20-Окт-09, (0) [смотреть все]

Сообщения [Сортировка по времени | RSS]


31. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Heckfy (ok), 21-Окт-09, 01:42 
octaword summa() {
long two_power_63 = 9223372036854775808;
return (1+2*two_power_63)*(two_power_63);
}

И это я еще не оптимизировал по времени. :-)
А ведь зная, что там будут сплошные операции сдвига и сумма, я могу представить это массивом, заполненным нулями, старший бит всей последовательности в нотации платформы равен единице.
В итоге, результатом сложения должно быть число, полученное сложением двух чисел:
0x40000000000000000000000000000000 и 0x4000000000000000
Число можно в данном случае получить и как битовую сумму, а можно просто на глаз прикинуть: 0x40000000000000004000000000000000

Погрешность моего предсказания велика, но смею предположить, что на ассемблере Z80 это вычисление заняло бы примерно 150 тактов генератора процессора, что выразилось бы в 150/(3.5E6) секунд процессорного времени. Что дает мне право сделать ошибку и посчитать не за 150 тактов, а в 3.5 раза дольше, дабы уложиться в лимит времени.

А так, задача красивая.

Ответить | Правка | К родителю #11 | Наверх | Cообщить модератору

33. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от pavlinux (ok), 21-Окт-09, 02:02 
>octaword summa() {
> long two_power_63 = 9223372036854775808;
> return (1+2*two_power_63)*(two_power_63);
>}
>В итоге, результатом сложения должно быть число, полученное сложением двух чисел:
>0x40000000000000000000000000000000 и 0x4000000000000000
>Число можно в данном случае получить и как битовую сумму, а можно просто на глаз прикинуть: 0x40000000000000004000000000000000

40000000000000008000000000000000

Дык, а где ж  простые? :)

Ответить | Правка | Наверх | Cообщить модератору

60. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от dot_kkursor (ok), 21-Окт-09, 22:24 
Ну зачем такие вещи пейсать, а.. :(
Пришёл вечером, набросал... ругайте и пользуйтесь:

// (c) .kkursor, 2009
// This code is licensed under WTFPL v.2, available at http://sam.zoy.org/wtfpl/

#include <stdio.h>
#define true 1
#define false 0

long int input (void) {
  long int a=-1;
  printf("Prime number sum calculator\nCopyright (c) .kkursor 2009\nThis code is licensed under WTFPLv2.\n\n");
  while (a < 0) {
        printf("Enter the maximum number you want to use in finding and summing prime numbers: ");
      scanf("%ld", &a);
      printf("\n");
  }
  return a;
}

long int find_prime (long int number) // find the following prime number
{
  long int i, current_num, remain;
  current_num = number+1;
  while (true != false)
  {
     for (i=2; i<current_num; i++)
     {
       remain = current_num%i;
       if (remain == 0) // the number is not prime
           break;
     }
     if (remain != 0)
       break;
     else
       current_num++;
  }
  return current_num;
}

int main (void) {
  long int limit, i=0, sum=0, current_number;
  limit = input();
  if (limit <= 2)
  {
      printf("There are no prime numbers in this range.\n");
      return 0;
  }
  printf("Calculating...\n");
  current_number = 2;
  while (true != false)
  {
    if (current_number >= limit)
          break;
    printf ("Found prime number: %ld\n", current_number);
    current_number = find_prime (current_number);
    sum += find_prime (current_number);
  }
  printf("The sum of prime numbers from 1 to %ld is %ld\n", limit, sum);
  return 1;
}

Сижу сейчас, считаю на своём Celeron M 1.73 до 2^32 для начала...

Ответить | Правка | Наверх | Cообщить модератору

61. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Карбофос (ok), 21-Окт-09, 22:59 
ой! а не проще битовыми полями? решение влоб не всегда самое быстрое :)
к тому же деление в цикле....
Ответить | Правка | Наверх | Cообщить модератору

62. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от dot_kkursor (ok), 21-Окт-09, 23:01 
>ой! а не проще битовыми полями? решение влоб не всегда самое быстрое
>:)
>к тому же деление в цикле....

Не стреляйте больно, я только начинаю си изучать. :)
Щас пытаюсь приделать к ней вывод remaining % по запросу - не получается :(((

Ответить | Правка | Наверх | Cообщить модератору

64. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 21-Окт-09, 23:41 
да это не критика. :)
операция деления выполняется примерно в 4 раза медленнее операции умножения. ну и остаток от деления - тоже. поэтому надо избегать медленной операции, поэтому нужен массив с true/false, который будет указывать на принадлежность к простому числу, или нет. ;)
Ответить | Правка | Наверх | Cообщить модератору

66. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от dot_kkursor (ok), 22-Окт-09, 00:18 
>да это не критика. :)
>операция деления выполняется примерно в 4 раза медленнее операции умножения. ну и
>остаток от деления - тоже. поэтому надо избегать медленной операции, поэтому
>нужен массив с true/false, который будет указывать на принадлежность к простому
>числу, или нет. ;)

Каких же размеров должен быть этот массив... предлагаете на каждое число по элементу? Но всё равно же придётся тогда определять, простое оно или нет, с помощью цикла с делением с остатком... А как иначе?
А торможение заметно очень. Первые несколько десятков тысяч чисел перебирает очень шустро, а потом всё медленнее и медленнее...

Ошибок ещё нашёл логических несколько в коде, неправильно считало, вот с исправлением:
// (c) .kkursor, 2009
// This code is licensed under WTFPL v.2, available at http://sam.zoy.org/wtfpl/

#include <stdio.h>
#define true 1
#define false 0

unsigned long int input (void) {
  unsigned long int a=0;
  printf("Prime number sum calculator\nCopyright (c) .kkursor 2009\nThis code is licensed under WTFPLv2.\n\n");
  while (a == 0) {
        printf("Enter the maximum number you want to use in finding and summing prime numbers: ");
      scanf("%ld", &a);
      printf("\n");
  }
  return a;
}

unsigned long int find_prime (unsigned long int number) // find the following prime number
{
  unsigned long int i, current_num, remain;
  current_num = number+1;
  while (true != false)
  {
     for (i=2; i<current_num; i++)
     {
       remain = current_num%i;
       if (remain == 0) // the number is not prime
           break;
     }
     if (remain != 0)
       break;
     else
       current_num++;
  }
  return current_num;
}

int main (void) {
  unsigned long int limit, i=0, sum=0, current_number;
  limit = input();
  if (limit < 2)
  {
      printf("There are no prime numbers in this range.\n");
      return 0;
  }
  printf("Calculating...\n");
  current_number = 1;
  while (true != false)
  {
  current_number = find_prime (current_number);
    if (current_number >= limit)
          break;
    printf ("Found prime number: %ld\n", current_number);
    sum += current_number;
  }
  printf("The sum of prime numbers from 1 to %ld is %ld\n", limit, sum);
  return 1;
}

Но всё равно, блин, не получается большие числа считать... 225263 - последнее простое число, которое может прибавиться, не превратив сумму неизвестно во что...

Ответить | Правка | Наверх | Cообщить модератору

67. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 22-Окт-09, 01:04 
для каждого числа нужен всго лишь один бит. потом, массив можно немного сократить. и прочие трюки встроить. скажем, грубо операция деления в несколько раз медленнее операции доступа к памяти. по крайней мере - в твоем решении.

в 1 мегабайте памяти можно уместить 1024х1024 чисел. ну и так далее.

но это даже не единственное решение.
просто найденное тобой решение это как метод сортировки пузырьком в сравнении с другими алгоритмами сортировки.

Ответить | Правка | Наверх | Cообщить модератору

68. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 22-Окт-09, 08:39 
при битовой кодировке - 1024х1024х8х2 чисел. все четные можно выкинуть
Ответить | Правка | Наверх | Cообщить модератору

69. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от dot_kkursor (ok), 22-Окт-09, 09:09 
>при битовой кодировке - 1024х1024х8х2 чисел. все четные можно выкинуть

Всё равно же делить на 2 %)
Или типа если младший бит 0, то выкинуть нафиг? Побитовые операции, если мне не изменяет мой склероз, выполняются гораздо быстрее...

Ответить | Правка | Наверх | Cообщить модератору

70. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Карбофос (ok), 22-Окт-09, 09:38 
конечно гораздо быстрее, особенно в конвейере, если развернутый цикл, к примеру. или если компилятор его смог развернуть.
Ответить | Правка | Наверх | Cообщить модератору

72. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 22-Окт-09, 10:20 
ускоряем твой алгоритм в 2 раза:

for (i=3; i<current_num; i+=2){
  remain = current_num%i;
  if (remain == 0) // the number is not prime
    break;
}

можешь еще одну проверку встроить

Ответить | Правка | Наверх | Cообщить модератору

63. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от dot_kkursor (ok), 21-Окт-09, 23:05 
>ой! а не проще битовыми полями? решение влоб не всегда самое быстрое
>:)
>к тому же деление в цикле....

А как без деления в цикле можно определить "простоту" числа?
Обнаружил, что несмотря на введённое в прогу 4294967296 (2^32) она понимает ровно в пополам меньше - (2^31-1). Блджад.
А это значит, что она не будет считать даже до (2^31-1), не говоря уже до 2^64.
pavlinux, современные компьютеры это не умеют!
Или я криворук :(

Ответить | Правка | К родителю #61 | Наверх | Cообщить модератору

65. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 21-Окт-09, 23:46 
нарисуй алгоритм на бумаге. скажем, определение простых чисел до 40 начиная с двойки
двойка: зачеркиваем 4, 6, 8, 10...
тройка: зачеркиваем 6, 9, 12, 15...
пять: 10, 15, 20, 25...
семь: 14, 21, 28...
ну и т.д.
уже зачеркнутнутые можно не зачеркивать ;)
Ответить | Правка | Наверх | Cообщить модератору

71. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 22-Окт-09, 09:39 
даже узнал, как алгоритм называется: сечение Эратосфена
Ответить | Правка | Наверх | Cообщить модератору

73. "В ядро Linux может быть включен диспетчер реального времени"  +1 +/–
Сообщение от Карбофос (ok), 22-Окт-09, 10:40 
си вообще-то разрешает использовать числа ling long int или __int64
Ответить | Правка | К родителю #63 | Наверх | Cообщить модератору

74. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Карбофос (ok), 22-Окт-09, 10:41 
long long int
Ответить | Правка | Наверх | Cообщить модератору

75. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от pavlinux (ok), 23-Окт-09, 03:44 
>[оверквотинг удален]
>>:)
>>к тому же деление в цикле....
>
>А как без деления в цикле можно определить "простоту" числа?
>Обнаружил, что несмотря на введённое в прогу 4294967296 (2^32) она понимает ровно
>в пополам меньше - (2^31-1). Блджад.
>А это значит, что она не будет считать даже до (2^31-1), не
>говоря уже до 2^64.
>pavlinux, современные компьютеры это не умеют!
>Или я криворук :(

"Всё украдено уже до нас" (с) Ы

#include <limits.h>
#include <gmp.h>

int main (int argc, char **argv)
{
  mpz_t x, sum;
  unsigned long long int i, j, k;

  mpz_init (x);
  mpz_init (sum);

        for (i = 0; i < ULLONG_MAX; i++) { /* ULLONG_MAX = (2^64) - 1 */
        for (j = 0; j < ULLONG_MAX; j++) {

            k = i + j;
            mpz_init_set_ui(x, k);
            if ( mpz_probab_prime_p (x, 10) == 2 ) {
                mpz_add(sum, x, sum);
           }
          }
        }
  gmp_printf("%Zd\n", sum);
  mpz_clear (x);
  mpz_clear (sum);
  return 0;
}


# gcc-4.4.2 isprime.c -lgmp
# time ./a.out &
# echo "Курить...."


Бенчмарк для тех, кто орёт с 8 Gb оператифки своп не нужен!!! :)


Ответить | Правка | К родителю #63 | Наверх | Cообщить модератору

76. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Карбофос (ok), 23-Окт-09, 10:02 
ну это же процесс творческий ;)

сколько он там памяти аллокирует? O_o для 64 бит

примерно базировано на подобном алгоритме:


// http://www.fpx.de/fp/Software/sieve.c
//
#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define TEST(f,x)    (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define SET(f,x)    *(f+(x)/16)|=1<<(((x)%16L)/2)

int
main(int argc, char *argv[])
{
  unsigned char *feld=NULL, *zzz;
  unsigned long teste=1, max, mom, hits=1, count, alloc, s=0, e=1;
  time_t begin;

  if (argc > 1)
    max = atol (argv[1]) + 10000;
  else
    max = 14010000L;

  while (feld==NULL)
        zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

  for (count=0; count<alloc; count++) *zzz++ = 0x00;

  printf ("Searching prime numbers to : %ld\n", max);

  begin = time (NULL);
  while ((teste+=2) < max)
        if (!TEST(feld, teste)) {
                if  (++hits%2000L==0) {printf (" %ld. prime number\x0d", hits); fflush(stdout);}
                for (mom=3L*teste; mom<max; mom+=teste<<1) SET (feld, mom);
                }

  printf (" %ld prime numbers foundn %ld secs.\n\nShow prime numbers",
          hits, time(NULL)-begin);

  while (s<e) {
        printf ("\n\nStart of Area : "); fflush (stdout); scanf ("%ld", &s);
        printf ("End   of Area : ");     fflush (stdout); scanf ("%ld", &e);

        count=s-2; if (s%2==0) count++;
        while ((count+=2)<e) if (!TEST(feld,count)) printf ("%ld\t", count);
        }
  free (feld);
  return 0;
}

Ответить | Правка | Наверх | Cообщить модератору

77. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от pavlinux (ok), 23-Окт-09, 10:36 
/*  
*  Для прогрева всех ядрывшек, теперь c OpenMP
*   gcc-4.4.2 primesum.c -std=gnu99 -O3 -ffast-math -lgmp -fopenmp -o pimesum
*/

#include <gmp.h>

#define POW2_128 "340282366920938463463374607431768211456"

int main (int argc, char **argv)
{
  int k;
  mpz_t i, sum;
  mpz_t LIMIT;

  mpz_init (i);
  mpz_init (sum);
  mpz_init_set_str(LIMIT, POW2_128, 10);

#pragma omp parallel
{
#pragma omp do private (i, k)
                do {
                    mpz_add_ui(i, i, 1ULL);
                    k = mpz_cmp(LIMIT, i);
                    if (mpz_probab_prime_p (i, 10) == 2 ) {
#pragma omp shared (sum)
#pragma omp critical (sum)
                      mpz_add(sum, i, sum);
                      gmp_printf("Prime: %Zd, Sum  %Zd\n", i, sum);
#pragma omp flush(sum)
                   }
               } while ( k != 0 );
#pragma omp end parallel
}
  gmp_printf("%Zd\n", sum);
  mpz_clear (i);
  mpz_clear (sum);

return 0;
}

Ответить | Правка | Наверх | Cообщить модератору

78. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Карбофос (ok), 23-Окт-09, 11:06 
в принципе, просто использовать битовые массивы (сечение) - тоже решение "в лоб". проблема с нерациональным использованием памяти - налицо.
Ответить | Правка | Наверх | Cообщить модератору

79. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от pavlinux (ok), 23-Окт-09, 18:08 
>в принципе, просто использовать битовые массивы (сечение) - тоже решение "в лоб".
>проблема с нерациональным использованием памяти - налицо.

Уж поверь, в GMP над этим поработали.
Если глянешь исходники, там все увидишь, и битовые, и спец малоки,...

Так вот, теперь надо чтоб эта программка работала ровно, ну скажем 1300 мс +/- 30 мс.

Ответить | Правка | Наверх | Cообщить модератору

83. "В ядро Linux может быть включен диспетчер реального времени"  +/–
Сообщение от Карбофос (ok), 24-Окт-09, 12:25 
доверяй,но проверяй. ;)
качнул исходники с докой из репозитория. мерси за инфу.
Ответить | Правка | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей 		Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру