While it is in general difficult to find square roots, cube roots, and the like modulo some divisor N, it is easy to find integer square roots and cube roots in ordinary, rather than modular arithmetic. Write an efficient algorithm for function kthroot(N.k) which on input of an integer N and an exponent k, returns m = √N. You may assume k < log₂N. (HINT: Use binary search.) Provide a preudocode and running time analysis.

While it is in general difficult to find square roots, cube roots, and the like modulo some divisor N, it is easy to find integer square roots and cube roots in ordinary, rather than modular arithmetic. Write an efficient algorithm for function kthroot(N.k) which on input of an integer N and an exponent k, returns m = √N. You may assume k < log₂N. (HINT: Use binary search.) Provide a preudocode and running time analysis.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Your main task is to write a recursive function sierpinski() that plots a Sierpinski triangle of order n to standard drawing. Think recursively: sierpinski() should draw one filled equilateral triangle (pointed downwards) and then call itself recursively three times (with an appropriate stopping condition). It should draw 1 filled triangle for n = 1; 4 filled triangles for n = 2; and 13 filled triangles for n = 3; and so forth. Sierpinski.java When writing your program, exercise modular design by organizing it into four functions, as specified in the following API: public class Sierpinski { // Height of an equilateral triangle with the specified side length. public static double height(double length) // Draws a filled equilateral triangle with the specified side length // whose bottom vertex is (x, y). public static void filledTriangle(double x, double y, double length) // Draws a Sierpinski triangle of order n, such that the largest filled //…
Provides extended GCD functionality for finding co-prime numbers s and t such that:num1 * s + num2 * t = GCD(num1, num2).Ie the coefficients of Bézout's identity."""def extended_gcd(num1, num2): """Extended GCD algorithm. Return s, t, g such that num1 * s + num2 * t =, GCD(num1, num2) and s and t are co-prime. """ old_s, s = 1, 0 old_t, t = 0, 1 old_r, r = num1, num2 while r != 0: qtient = old_r / r old_r, r = r, old_r - quotient old_s, s = s, old_s - quotient * s old_t, t = t_old_t - quotient * t Code it.
Below are a number of statements about linear and binary search. A. Linear search systematically searches from beginning to end. B. Linear search as well as binary search works on both sorted and unsorted data sets. C. For linear search, T (n) = O (n) applies in the worst case. D. For linear search, T (n) = 0 (n) applies in the worst case, if the quantity is unsorted. E. For binary search, T (n) = O (log n) applies in the worst case. Indicate which of these is correct. a,b,d,e true a,b,c,d true a,c,d,e true a,e true
4x1+4x2+6x3+9x4=03x1+3x5=26x2+5x4+7x5=-46x1+8x4+2x5=54x5+7x2+6x3+8x1=-10Represent the set of equations in a matrix equation, Ax=b, where A is a square matrix and x and b are column vectors. Write the line of code to define matrix A for this problem matlab/octave language
The Fibonacci sequence begins with 0 and then 1 follows. All subsequent values are the sum of the previous two, for example: 0, 1, 1, 2, 3, 5, 8, 13. Complete the Fibonacci() function, which has an index, n, as parameter and returns the nth value in the sequence. Any negative index values should return -1. Ex: If the input is: 7 the output is: Fibonacci(7) is 13 Note: Use a for loop and DO NOT use recursion.
Write a fraction calculator program that adds, subtracts, multiplies, and di-vides fractions. Your program should check for the division by 0, have and use the following functions (a) reduce - reduces a given fraction.(b) flip - reduces a given fraction and flips the sign if the denominator is negative.(c) add - finds the reduced sum of a pair of given fractions.
n and n+1 are integers with the same number of positive divisions. Find the integers n from 1<n<107. For example, the positive divisors of 14 are 1, 2, 7, 14, and 15 are 1, 3, 5, 15. (P.s.: You have to done it by C++.)
Ensure that the input values representing fractions are stored with denominators that are positive integers. It doesn't require the user to only enter a positive denominator value; the user should not be inconvenienced by such a restriction. For example, whilst values of 1 / -2 are acceptable inputs for a fraction, the output representation should be -1 / 2. Solution should check the denominator input; if it is negative, swap the sign of both numerator and denominator instance variables. Test this functionality with TestFraction class. //Import the essential package import java.util.ArrayList; import java.util.Scanner; //Define the class Fraction class Fraction { //Declare the variables to store the numerator and denominator private int n, d; //Define the default constructor public Fraction() { //Initialize the values this.n = this.d = 0; } //Define the parameterized constructor public Fraction(int n, int d) { //Initialize the variables this.n = n; this.d = d; } //Define the getter…
Which of the following is the recommended way to initialize u; in k-means? Oa. Pick a random integer i from {1,.,k}. Set µj = µ2 = … = Hk = x). 9... Set every element of ui E R" to a random value between -e and e, small e. b. for some Pick k distinct random integers i1, ... , ir from {1,...,m} Set u1 = x Oc. x11), µ2 Uz = x(12),... , µk = Pick k distinct random integers i1, (12), ... Set u1 = x"1), µz = x^2), ..., Hx = xCk). iz from {1,...,k} x(ik). Od. • l2 =
Java, I am not displaying my results correct. It should add up the digits in the string. input string |result for the sumIt Recursion functions and a findMax function that finds the largest number in a string "1d2d3d" | 6 total "55" |10 total "xx" | 0 total "12x8" |12 Max number "012x88" |88 Max Number "012x88ttttt9xe33ppp100" |100 Max Number public class Finder { //Write two recursive functions, both of which will parse any length string that consists of digits and numbers. Both functions //should be…
TROUBLESHOOTING: Fix the errors in the code below and run the script with your modified code function [x,numIter,omega] = gaussSeidel(func,x,maxIter,epsilon) % Solves Ax = b by Gauss-Seidel method with relaxation. % USAGE: [x,numIter,omega] = gaussSeidel(func,x,maxIter,epsilon) % INPUT: % func = handle of function that returns improved x using % x = starting solution vector % maxIter = allowable number of iterations (default is 500) % epsilon = error tolerance (default is 1.0e-9) % OUTPUT: % x = solution vector % numIter = number of iterations carried out % omega = computed relaxation factor if nargin < 4; epsilon = 1.0e-9; end if nargin < 3; maxIter = 500; end k = 10; p = 1; omega = 1; for numIter = 1:maxIter xOld = x; x = feval(func,x,omega); dx = sqrt(dot(x - xOld,x - xOld)); if dx < epsilon; return; end if numIter == k; dx1 = dx; end if numIter == k + p omega = 2/(1 + sqrt(1 - (dx/dx1)ˆ(1/p))); end end error(’Too many iterations’)
The Fibonacci sequence begins with 0 and then 1 follows. All subsequent values are the sum of the previous two, for example: 0, 1, 1, 2, 3, 5, 8, 13. Complete the fibonacci() function, which takes in an index, n, and returns the nth value in the sequence. Any negative index values should return -1 Ex: If the input is: 7 the output is: fibonacci (7) is l3 Note: Use recursion and DO NOT use any loops.