Целая часть квадратного корня
Подскажите, как вытащить целую часть из-под квадратного корня?
Например, sqrt(12)=2*sqrt(3), sqrt(50)=5*sqrt(2). Не нашёл реализации на javascript :-E |
Цитата:
|
Цитата:
Наверное, не достаточно чётко объяснил, что за целая часть. Нужен алгоритм представления числа n в виде k^2*m. |
Цитата:
Максимальный целочисленный множитель 1.Составляем массив сомножителей подкоренного выражения и ищем среди них наибольший квадрат |
Цитата:
Цитата:
|
function Tstsqrt(Z) {
var a = parseInt(Math.sqrt(Z));
if(a<2) return false;
for(var i=a; i>=2; i--){
if(parseInt(Z/(i*i))==Z/(i*i)){
return (''+i+'*sqrt('+Z/(i*i)+')');
}
} return false;
}
alert(Tstsqrt(12))
alert(Tstsqrt(50))
alert(Tstsqrt(1000))
alert(Tstsqrt(99998))
alert(Tstsqrt(1998))
|
Deff,
Сравним скорость? ;)
// ------------------------------ Моё ------------------------------
var factorize = ( function ( maxNumber ) {
var primesMapSize = Math.ceil( Math.sqrt( maxNumber ) );
var primesMap = [ void 0, true ];
var primesList = [];
for ( var number = 2; number <= primesMapSize; number++ ) {
if ( primesMap[ number ] === false ) {
continue;
}
primesList.push( number );
primesMap[ number ] = true;
for ( var next = number * 2; next <= primesMapSize; next += number ) {
primesMap[ next ] = false;
}
}
maxNumber = primesMapSize * primesMapSize;
return function ( number ) {
if ( !isFinite( number = +number ) || number < 1 || number != Math.floor( number ) ) {
return Number.NaN;
}
if ( number > maxNumber ) {
return false;
}
if ( number == 1 ) {
return [];
}
if ( number <= primesMapSize && primesMap[ number ] == true ) {
return [ { factor : number, times : 1 } ];
}
var maxPrime = Math.floor( Math.sqrt( number ) );
var prime;
var primeId = 0;
var factor;
var factors = [];
while ( ( prime = primesList[ primeId++ ] ) <= maxPrime ) {
if ( number % prime == 0 ) {
factors.push( factor = { factor : prime, times : 1 } );
while ( ( number /= prime ) % prime == 0 ) {
factor.times++;
}
if ( number == 1 ) {
return factors;
}
maxPrime = Math.floor( Math.sqrt( number ) );
}
}
factors.push( { factor : number, times : 1 } );
return factors;
};
})( Math.pow( 2, 40 ) );
function normalizeSqrt ( number ) {
var factors = factorize( number );
if ( typeof factors == "number" && isNaN( factors ) ) {
return "invalid number";
}
if ( factors === false ) {
return "number too big";
}
var rational = 1;
var irrational = 1;
var factor;
while ( factor = factors.pop() ) {
rational *= Math.pow( factor.factor, factor.times >> 1 );
if ( factor.times & 1 ) {
irrational *= factor.factor;
}
}
return rational + " * sqrt( " + irrational + " )";
}
// ------------------------------ Deff'а ------------------------------
function Tstsqrt(Z) {
var a = Math.floor(Math.sqrt(Z));
if(a<2) return false;
for(var i=a; i>=2; i--){
var j=Z/(i*i);
if(Math.floor(j)==j){
return (i+' * sqrt( '+j+' )');
}
} return false;
}
// ------------------------------ Бенчмарк ------------------------------
var numbers = [
906972642240,
1099505336329,
1099505336330,
1099505336331,
1099505336332,
1099505336333,
Math.pow( 2, 40 ) - 1
];
function test ( title, func ) {
var result = title + "\n\n";
var timeStart = +new Date();
for ( var i = 0; i < numbers.length; i++ ) {
result += numbers[ i ] + " : " + func( numbers[ i ] ) + "\n";
}
result += "\nTime: " + ( ( +new Date() - timeStart ) / 1000 ).toFixed( 3 ) + " sec.";
return result;
}
alert( test( "normalizeSqrt", normalizeSqrt ) + "\n\n\n\n" + test( "Tstsqrt", Tstsqrt ) );
|
Дзен-трансгуманист,
А время на формирование var factorize ??? |
Дзен-трансгуманист +(Плусы не ставяцо),
:) У мну разница на порядок, - (в принципе приемлимо, если задачка не частая... Первое воплощение должно быть прозрачно для юзера (*Ксать снежок понравился Скрин:  |
рони,
Это одноразовая операция, создается список простых чисел с расчетом на многократное использование функции без перезагрузки страницы. Но если так принципиально, измерения под катом:
function create ( maxNumber ) {
var primesMapSize = Math.ceil( Math.sqrt( maxNumber ) );
var primesMap = [ void 0, true ];
var primesList = [];
for ( var number = 2; number <= primesMapSize; number++ ) {
if ( primesMap[ number ] === false ) {
continue;
}
primesList.push( number );
primesMap[ number ] = true;
for ( var next = number * 2; next <= primesMapSize; next += number ) {
primesMap[ next ] = false;
}
}
maxNumber = primesMapSize * primesMapSize;
return function ( number ) {
if ( !isFinite( number = +number ) || number < 1 || number != Math.floor( number ) ) {
return Number.NaN;
}
if ( number > maxNumber ) {
return false;
}
if ( number == 1 ) {
return [];
}
if ( number <= primesMapSize && primesMap[ number ] == true ) {
return [ { factor : number, times : 1 } ];
}
var maxPrime = Math.floor( Math.sqrt( number ) );
var prime;
var primeId = 0;
var factor;
var factors = [];
while ( ( prime = primesList[ primeId++ ] ) <= maxPrime ) {
if ( number % prime == 0 ) {
factors.push( factor = { factor : prime, times : 1 } );
while ( ( number /= prime ) % prime == 0 ) {
factor.times++;
}
if ( number == 1 ) {
return factors;
}
maxPrime = Math.floor( Math.sqrt( number ) );
}
}
factors.push( { factor : number, times : 1 } );
return factors;
};
}
// ------------------------------ Бенчмарк ------------------------------
var numbers = [
Math.pow( 2, 20 ),
Math.pow( 2, 30 ),
Math.pow( 2, 40 )
];
function test ( maxNumber ) {
var timeStart = +new Date();
var factorize = create( maxNumber );
return "maxNumber : " + maxNumber + ", time : " + ( ( +new Date() - timeStart ) / 1000 ).toFixed( 3 ) + " sec.";
}
for ( var i = 0, result = ""; i < numbers.length; i++ ) {
result += test( numbers[ i ] ) + "\n";
}
alert( result );
Цитата:
Цитата:
|
| Часовой пояс GMT +3, время: 12:16. |