Linux за българи: Форуми

Здравейте. Тъй като нямам права за писане в раздела със задачките, моля правоимащите да преместят тази тема там, а този ред - да бъде изтрит.

Всички знаем за функцията abs(int x) която е математическото представяне на абсолютната стойност на дадена променлива (от целочислен тип), която присъства в (да не кажа всеки) почти всеки език.

Задачката е следната:

"Да се напише на любим за Вас език функция abs(), към която може да се добавя един аргумент (целочислена стойност), връщаща (отново) целочислена стойност.

Каква е уловката?

- Да не се използва if (така че случая с if (a < 0) return a*-1 - отпада), switch и всякакви вариации на : ? (в PHP) && || и т.н.
- Да не се създават никакви променливи във функцията abs()

Решението на "гатанката" ще бъде публикувано след 7 дни, считано от датата и часа на пускане на темата (освен ако някой не се е добрал до него първи, при което темата ще бъде заключена с флаг "Solved").

Дерзайте!  ;D

sqrt(a^2) !?

Просто:

GeSHi (C):
unsigned int abs(int x)
{
   return (x + (x >> 31)) ^ (x >> 31);
}
 

http://en.wikipedia.org/wiki/Two%27s_complement

sqrt(a^2) !?

Компилирано под C++, при a=3, извежда 1... (моля вписвайте пълните решения + езика на който е написана)

Просто:

Цитат

unsigned int abs(int x)
{
   return (x + (x >> 31)) ^ (x >> 31);
}

http://en.wikipedia.org/wiki/Two%27s_complement

Извежда правилно решение което означава че имаме вече един отговор.

Продължавайте... Други идеи?

 асемблер за Microchip контролер

       cblock 0x20
       integ
       integ_abs
       endc

 MainLoop:
       ...
       movf integ,w        ; записва стойността на променливата integ в w регистъра
       call   abs              ; извиква подпрограма за изчисляване на абсолютната стойност на integ
       movwf integ         ; записва върната абсолютна стойност обратно в integ променливата
       ...

 abs:
       movwf  integ_abs  ; прехвърля съдържанието на w регистъра в променливата integ_abs
       btfsz     status,z    ; проверява за 0, ако съдържанието на w е нула, то и абсолютната стойност е 0, ако да - излизане от
                                  ; подпограмата, ако не е нула - следващия оператор се прескача
       return
       btfss     integ_abs,7 ; проверява най-старшия бит, ако е 0 то числото е положително, следователно и абсолютната му стойност е същата
                                    ; ако е отрицателно - следващия оператор се прескача, ако е положително - изход от подпрограмата
       return
       xorlw    0xff          ; изключващо "или" на съдържанието на w регистъра с 0xff, резултатът се записва обратно в w регистъра
       addlw    0x01        ; съдържанието на w се събира с 1 , т.е. увеличава се с 1, резултатът се записва в w регистъра
       return                  ; изход от подпрограмата. Резултатът се съдържа в w регистъра и се извлича от там


       пример
       
       integ = -127 (10000001)
       10000001 xor 11111111 = 01111110 (126)
       увеличено с 1 = 127

       пример 2

       integ = -2 (11111110)
       11111110 xor 11111111 = 00000001 (1)
       увеличено с 1 = 2

 това последното го пуснах на майтап като отговор на условието "да се напише на любим програмен език". Програмата би трябвало да работи, но не е спазено едно от условията - да не се използва if - проверката на битовете в специалните регистри си е един вид if при езиците от по-високо ниво.

това последното го пуснах на майтап като отговор на условието "да се напише на любим програмен език". Програмата би трябвало да работи, но не е спазено едно от условията - да не се използва if - проверката на битовете в специалните регистри си е един вид if при езиците от по-високо ниво.

Или го пусна да се изфукаш, че можеш да пишеш на асемблер!

sqrt(a^2) !?

sqrt(a**2)

Колеги кой ви е бил по главата да използвате такива сложни функции като корен квадратен, а не
използвате само булева функция AND с константа  :)

GeSHi (C):
unsigned int abs (unsigned int x)
{
return (x&konstanta);
}

Не мисля че е възможно, поне по начина по който се представят signed integer-ите в "модерните" архитектури. Би могло ако се представяха по следният начин:

[sign bit][stoinost]

и примерно 000000001 e 1, а 10000001 e -1. Това изглежда безкрайно логично и просто, но не се ползва. Ако все пак се ползваше, тогава абсолютната стойност се смята лестно, примерно с AND:

return (x&0x7FFFFFFF);

Или с две побитови отмествания:

return ((x>>1)<<1);

На php:

GeSHi (PHP):
function xabs($x){
	return (int) sqrt(pow($x,2));
}

GeSHi (PHP):
function xabs($x){
	return (int) substr(sprintf("%+d",$x),1);
}

Само че не става ясно някакъв хитър математически начин ли се търси, нещо по-бързо от стандартната abs() (за конкретен език) или да се ползва страничен ефект от записването на променливите (пак в конкретен език)?

Цитат на: H. Paskalev в Jul 17, 2011, 01:18

sqrt(a^2) !?

sqrt(a**2)

Не съм имал предвид синтаксис на конкретен език... Предложих решение с израз - корен от квадрат на x.
Но определено решението с побитови операции е по-елегантно, макар и относително. :)

П.П. А сега се досетих, че може би просто предлагаш решение в Perl или друг език. :D

Цитат на: bot в Jul 17, 2011, 03:54

това последното го пуснах на майтап като отговор на условието "да се напише на любим програмен език". Програмата би трябвало да работи, но не е спазено едно от условията - да не се използва if - проверката на битовете в специалните регистри си е един вид if при езиците от по-високо ниво.

Или го пусна да се изфукаш, че можеш да пишеш на асемблер!

 Така е! Ако искаш мога да ти напиша горния фрагмент на асемблер за Атмел, Silicon Labs процесори или 8051 базирани. Ей сега вече ще мога да спя по-спокойно.
 
 пп споменах ли #C

Спомена.

Всичко си зависи от архитектурата и всичко може да се разбие винаги на по-малък код, но на ниско ниво (асемблер например) не е възможно да не се използват регистри (променливи), а и в условието не е споменато какъв е типът на думата и архитектурата така че за мен *2.

отговорът за допълнителен код при интел архитектура е:

GeSHi (C):
unsigned int abs(int x)
{
return (x^(x>>31))+(((x>>31)+2)&0x1);
}
 

при този код:

GeSHi (C):
unsigned int abs(int x)
{
   return (x + (x >> 31)) ^ (x >> 31);
}
 

има грешка от препълване при което някои числа ще правят проблеми

Няма проблем при препълване, поне на x86 архитектура. Причината е че единственият случай в който имаме препълване е когато събираме 0xFFFFFFFF (-1) с 1 (ред. :глупости). На x86 архитектура, резултатът се wrap-ва и накрая имаме правилен резултат, защото xor-ваме с 1. (ред. : глупости, виж по-долния пост).

Но на други архитектури съм съгласен, може да има проблеми.

Колеги кой ви е бил по главата да използвате такива сложни функции като корен квадратен, а не
използвате само булева функция AND с константа  :)

Ето кого:

- Да не се използва if (така че случая с if (a < 0) return a*-1 - отпада), switch и всякакви вариации на : ? (в PHP) && || и т.н.
- Да не се създават никакви променливи във функцията abs()

Цитат на: H. Paskalev в Jul 17, 2011, 01:18

sqrt(a^2) !?

Компилирано под C++, при a=3, извежда 1...

Това как го получи  ????

Цитат на: LinuxFanUNIX в Jul 17, 2011, 01:27

Цитат на: H. Paskalev в Jul 17, 2011, 01:18

sqrt(a^2) !?

Компилирано под C++, при a=3, извежда 1...

Това как го получи  ????

В C++ този израз наистина връща 1, въпреки че с някои компилатори се изисква преработка, за да бъде компилиран. Връща единица, защото:
a = 3, записано в двоична система е 11, a 2 записано в двоична система е 10. Логическото изключващо "или"(^) на 11 и 10 връща единица.
Корен от 1 връща 1, но както казах не съм адресирал някой конкретен език, а само израз като решение...
Записването, което съм представил е присъщо за системи като Mathematica и Maple.

 Аз пък си мислех че със символът ^ се изразява повдигане на степен, а логическият еквивалент на повдигане на квадрат е "ротация наляво". Между другото това е най-елементарния начин за намиране на абсолютна стойнот - корен квадратен от повдигнато на квадрат число.

 говоря глупости, с ротация наляво се изразява умножено по 2. Съжалявам!

Аз пък си мислех че със символът ^ се изразява повдигане на степен, а логическият еквивалент на повдигане на квадрат е "ротация наляво". Между другото това е най-елементарния начин за намиране на абсолютна стойнот - корен квадратен от повдигнато на квадрат число.

Както казах този символ се използва в някои системи за изразяване на повдигане на степен, но не и в повечето програмни езици(в частност C++).
Наистина това е най-елементарното решение, за което се сетих.
За побитовите операции може да се спретне доста дълга дискусия. Добре е да се покажат няколко решения, всяко си има плюсовете и минусите.
 [_]3 :)

 Това е голям проблем за езиците от високо ниво - никой не знае колко такта (процесорно време) отнема една функция, всичко зависи от това как компилаторът ще "смели" дадена команда на машинен код за съответния процесор. На мен ми се е налагало често да превключвам на асемблер дори когато пиша на #C за да оптимизирам една операция и да изравня времената при изчисление.  Примерно при кода, който съм дал по-нагоре, ако търсим абсолютна стойност на положително число изчислението ще приключи по-рано, което не е желателно, т.е. една подпрограма трябва да има точно определено време, независимо от това колко време ще отнемат отделните резултати. Често се налага да се добавят "празни" команди (NOP инструкция) за да се изравнят времената. Това е необходимо, когато се използва watchdog функцията - знаем че една подпрограма отнема да речем 10mS, ако процесорът се забави по-дълго това означава че е "забил" и watchdog хардуерът не получава навреме kick инструкция, тогава процесорът се рестартира, но не искаме това да се случи само защото конкретния резултат изисква малко по-дълго време за изчисление.

И това може да се превърне в огромна дискусия, а може би по-скоро поредната "кавга".
Език от ниско или високо ниво, "управляем" или не, интерпретиране или компилиране...
За всяко си има място под слънцето и привърженици.
Но съм съгласен, че забравата на начина, по който работи машината и нейния "майчин" език, определено е навредило доста.
Не може да се отрекат и облагите от съвременните методи на разработка, макар и често затъпяващи.

Хм глупости съм говорил, нещата били далеч по-сложни. Препълването на signed int се оказва че има undefined поведение и по стечение на обстоятелствата, gcc все пак го wrap-ва, както прави с unsigned целочислените операции. Доколкото разбирам, това е дефолтното поведение в gcc4.x. При това положение все пак съм прав. Ще опростя нещата - нека int е 3-битов тип и да направим една truth таблица...

Първите 4 колони са signed int стойности, където побитовото отместване е аритметично и "запазва" sign bit-а. последната колона е резултатът когато кастнем това до unsigned int (понеже abs() по задание трябва да връща unsigned int стойност)


x          |   (x>>31)  |  x+(x>>31) |  (x+(x>>31))^(x>>31) | (unsigned int)result
========================================
0 (000) | 0(000)      |  0(000)       | 0(000)                          | 0
1 (001) | 0(000)      |  1(001)       | 1(001)                          | 1
2 (010) | 0(000)      |  2(010)       | 2(010)                          | 2
3 (011) | 0(000)      |  3(011)       | 3(011)                          | 3
-4(100) | -1(111)    |  3(011)       | -4(100)                         | 4
-3(101) | -1(111)    | -4(100)       | 3(011)                          | 3
-2(110) | -1(111)    | -3(101)       | 2(010)                          | 2
-1(111) | -1(111)    | -2(110)       | 1(001)                          | 1


Всичко това разчита на факта, че (поне gcc) поради някаква причина под "undefined behaviour" предпочита да wrap-ва резултата при препълване, по същият начин както с unsigned int препълването. При мен това е при всички -O опции. Обаче това също така е нещо, което компилатора приема за правилно, в резултат на което горната сметка работи. С друг компилатор, може и да не е така.

Йей, още нещо забавно (и доста очаквано апропо). Ако човек погледне моята "truth табличка", ще забележи, че abs(-4) връща -4 ако не се кастне до unsigned int, понеже 4 няма представяне в signed вид. Абсолютно същото важи и за abs() функцията която идва с libc:

GeSHi (C):
#include <stdlib.h>
#include <stdio.h>
 
void main()
{
unsigned int a=0x80000000;
int b=a;
 
printf("abs(a)=%d\n",abs(a));
printf("(unsigned int)abs(a)=%u\n",b);
 
}

....

GeSHi (Bash):
 ./abs
abs(a)=-2147483648
(unsigned int)abs(a)=2147483648
 

Това поведение е очаквано де, не мисля, че има нещо по-правилно в случая.

Така че умната при ползване на abs() ехех...в един определен случай може да има изненада :)

GeSHi (PHP):
<?php
 
function _abs($a)
{
	return ($a >= 0) * $a + ($a < 0) * (- $a);
}
 
assert("_abs(2) === 2");
assert("_abs(1) === 1");
assert("_abs(0) === 0");
assert("_abs(-1) === 1");
assert("_abs(-2) === 2");
 

Решението е валидно за повечето популярни езици (може би при някои ще се наложи type cast към int на булевите изрази)

Цитат на: backtolife в Jul 17, 2011, 22:06

Цитат на: LinuxFanUNIX в Jul 17, 2011, 01:27

Цитат на: H. Paskalev в Jul 17, 2011, 01:18

sqrt(a^2) !?

Компилирано под C++, при a=3, извежда 1...

Това как го получи  ????

В C++ този израз наистина връща 1, въпреки че с някои компилатори се изисква преработка, за да бъде компилиран. Връща единица, защото:
a = 3, записано в двоична система е 11, a 2 записано в двоична система е 10. Логическото изключващо "или"(^) на 11 и 10 връща единица.
Корен от 1 връща 1, но както казах не съм адресирал някой конкретен език, а само израз като решение...
Записването, което съм представил е присъщо за системи като Mathematica и Maple.

Баси езика за писане на програми дето смята грешно!

GeSHi (SQL):
mysql> USE test
DATABASE changed
mysql> delimiter | 
mysql> CREATE DEFINER = 'CTEHATA'@'%' FUNCTION `new_abs`(anInt INTEGER(11))
    ->     RETURNS int(11)
    ->     DETERMINISTIC
    ->     CONTAINS SQL
    ->     SQL SECURITY INVOKER
    -> BEGIN
    ->   RETURN anInt*SIGN(anInt) ;
    -> END;
    -> |    
Query OK, 0 rows affected (0.04 sec)
 
mysql> delimiter ;
mysql> 
mysql> SELECT new_abs(0);
+------------+
| new_abs(0) |
+------------+
|          0 | 
+------------+
1 row IN SET (0.00 sec)
 
mysql> SELECT new_abs(1);
+------------+
| new_abs(1) |
+------------+
|          1 | 
+------------+
1 row IN SET (0.00 sec)
 
mysql> SELECT new_abs(-1);
+-------------+
| new_abs(-1) |
+-------------+
|           1 | 
+-------------+
1 row IN SET (0.00 sec)
 
mysql> SELECT new_abs(2147483647);
+---------------------+
| new_abs(2147483647) |
+---------------------+
|          2147483647 | 
+---------------------+
1 row IN SET (0.00 sec)
 
mysql> SELECT new_abs(-2147483647);
+----------------------+
| new_abs(-2147483647) |
+----------------------+
|           2147483647 | 
+----------------------+
1 row IN SET (0.00 sec)
 

SIGN  и аналогични функции има в много езици. Всички други варианти или страдат от проблеми с препълването, или са специфични за дадени компилатор/интерпретатор и архитектура и съответното представяне на отрицателни числа.
Отделно от това, при болшинството решения има неявно деклариране на променлива...

@CTEHATA поклон, поклон!

Решение на Perl:

GeSHi (Perl):
#!/usr/bin/perl
 
$n = $ARGV[0];
printf "%d\n", abs($n);
exit 0;
 
sub abs {
	($k) = @_;
	$k =~ s/\D//gi;
	return int($k);
}

::)

хайде сега да сметнете кое е по-бързо abs() или функцииката, която сте забъркали, като същевременно
си пеете песента на Дони и Момчил - "На кой му трябва това"

GeSHi (Bash):
#!/bin/sh
 
echo $1 | tr -d '-'
 
 

 ;D

хайде сега да сметнете кое е по-бързо abs() или функцииката, която сте забъркали, като същевременно
си пеете песента на Дони и Момчил - "На кой му трябва това"

"На кой му трябва това" ... излизане от шаблона, разчупване на мисленето и т.н. Ясно е, че резултатът от задачката сам по себе си е лишен от смисъл, но приомите, с които е постигнат не са.

Код

GeSHi (Bash):
#!/bin/sh
 
echo $1 | tr -d '-'
 
 

 ;D

PHP вариант:

GeSHi (PHP):
function _abs($a) { return intval(ltrim($a, '-')); }

GeSHi (Javascript):
    function abs_a(anInt)
	  {
		return Math.max(anInt,-anInt);
	  }
    alert(abs_a(-2));
 

Това май ще е най-близо до бързодействието на оригиналната функция  ;D

ХАХАХАХАХАХАХ!
Не мога да повярвам!
Ето това е още по-бързо:

GeSHi (Javascript):
   function abs_a(anInt)
      {
         // return anInt*-(anInt<0) + anInt*(anInt>0)
             return anInt*(anInt>0-anInt<0)
      }
 

Но и двата ми примера са по-бързи от вградената Math.abs()  поне за тестваните Firefox за x86_64 Linux, Firefox за Win XP32 и IE за XP 32!!!
тествайте и други браузери моля
http://jsperf.com/max-avsmax-b ($2)

П.П. Това май дава интересен пример за смисъла на упражненията за мозъка - могат да ни покажат неща, които не са ни и хрумвали, когато сме започвали да го размърдваме.

OpenCL :)

uint abs(int x)
{
  return bitselect((x>(-x)),-x,x);
}

Поне при AMD видеокарти обаче, това е безкрайно безсмислено. Там самата архитектура е направена с идеята за abs(). Всяка integer инструкция има modifiers на входните операнди, един от тях е да вземе абсолютната стойност. Това става без performance penalty. Гореописаният код е дооооста по-бавен, отколкото да ползваш abs().

хайде сега да сметнете кое е по-бързо abs() или функцииката, която сте забъркали, като същевременно
си пеете песента на Дони и Момчил - "На кой му трябва това"

По принцип е така. Като изключим елемента на човъркането (който е тоооолкова присъщ на линукс-хората), все пак мисля, че има ограничена практическа полза, когато гониш performance. Примерно аз съм виждал memcmp() имплементация, която работи по-бързо стига данните да са aligned и същата ми е свършила добра работа с password cracking глупостите. memcmp() по принцип не може да прави такива предположения и трябва да проверява. Ако двата региона памет, които сравняваш ти почват от адрес в паметта, кратен на 8 (на 64-битова архитектура) и имат дължина кратна на 8 (или си убеден че са pad-нати с нулеви байтове), можеш да кастваш към unsigned long long и да сравняваш и това е по-бързо по разбираеми причини. Не винаги компилатора и стандартните библиотеки ти осигуряват максимална производителност. И не винаги се налага да прибягваш до дивотии от сорта на inline assembly, за да изстискаш каквото може :)